Построим машину, которая, отправляясь от числа, воспринятого в стандартном положении, стирает все числа левее данного (если таковые имеются) до первого встречного промежутка из двух или более пустых ячеек и возвращается к стандартному положению первоначально воспринятого числа.
Для построения программы такой машины (по существу, «построить машину Тьюринга» означает построить ее программу) составим по аналогии с примером 10 схему работы этой машины (рис.).
Составим программу для этой машины (табл. 13).
Таблица 13
|
| s0
| |
|
| q1
| s0Лq2
| |Лq1
|
| q2
| q3
| q6
|
| q3
| s0Пq4
|
|
| q4
| s0Пq4
| |Пq5
|
| q5
| s0Лq0
| |Пq5
|
| q6
| s0Нq1
| s0Лq6
|
