Изменения

==Определение языка 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_{1D}</tex>, <tex>BH_{2N}</tex>, <tex>BH_{2D}</tex>, отличающиеся от <tex>BH_{1N}</tex> только детерминированностью машин Тьюринга (<tex>D</tex> - детерминированная, <tex>N</tex> - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).