83
правки
Изменения
Новая страница: «Классом NSPACE(f) по аналогии с DSPACE называется класс языков(задач), для которых сущ…»
Классом NSPACE(f) по аналогии с [[Класс DSPACE|DSPACE]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.
<tex>NSPACE(f(n)) = \{ L \mid \exists НМТ m : L(m)=L, \delta (m,x) \le f(|x|) \}</tex>.
<tex>NSPACE(f(n)) = \{ L \mid \exists НМТ m : L(m)=L, \delta (m,x) \le f(|x|) \}</tex>.
