Рассмотрим машину Тьюринга, которая по записи любого числа на ленте распознает, оно больше нуля или равно нулю. В первом случае машина в качестве результата выдает число 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
|
