Изменения
→Определение языка BH_{1N}
==Определение языка BH_{1N}==
Языком <tex>BH_{1N}</tex>(от англ. bounded halting unary) называется множество троек, где <tex>m</tex> - недетерминированная машина Тьюринга, <tex>x</tex> - входные данные и <tex>t</tex> - времея время в унарной системе счисления, таких, что <tex>m(x)=1</tex> и время работы машины <tex>m</tex> на входе <tex>x</tex> <tex>T(m, x)\le t</tex>.<tex>BH_{1N} = </tex> { <tex>\langle m, x, 1^{t} \rangle | m </tex> - недетерминированная машина Тьюринга, <tex>m(x)=1, T(m, x)\le t</tex> }.
Так же существуют языки <tex>BH_{1D}</tex>, <tex>BH_{2N}</tex>, <tex>BH_{2D}</tex>, отличающиеся от <tex>BH_{1N}</tex> только детерминированностью машин Тьюринга (<tex>D</tex> - детерминированная, <tex>N</tex> - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).
