210
правок
Изменения
Нет описания правки
|definition=<tex> \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \mid m </tex> {{---}} [[Недетерминированные вычисления|недетерминированная машина Тьюринга]], <tex> m(x) = 1, T(m,x) \leqslant t \rbrace </tex>.
}}
Расшифровывается как '''Bounded halting unary non-deterministic'''.То есть <tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает <tex>1</tex> за время <tex> T(m, x) \leqslant t </tex>и <tex> 1^{t} </tex> {{---}} запись <tex> t </tex> в унарной системе счисления.
{{Теорема
