27
правок
Изменения
Нет описания правки
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
