Рассмотрим машину Тьюринга, которая по записи любого числа на ленте распознает, оно больше нуля или равно нулю. В первом случае машина в качестве результата выдает число 1, записанное через одну пустую клетку справа от воспринимаемого числа, во втором — число 0, записанное также через одну пустую клетку справа от воспринимаемого числа.
Составим сначала схему работы этой машины (рис.).
В соответствии с этой схемой получим программу машины (табл. 12).
Таблица 12
| s0
| |
|
q1
| s0Лq2
| |Лq2
|
q2
| s0Нq3
| |Нq6
|
q3
| s0Пq4
| |Пq4
|
q4
| s0Пq5
| |Пq4
|
q5
| |Нq0
|
|
q6
| s0Пq7
| |Пq7
|
q7
| s0Пq8
| |Пq7
|
q8
| |Нq9
|
|
q9
| |Нq0
| |Пq9
|