Пример 1. Машина, увеличивающая данное число на единицу — машина «1». В начале работы головка воспринимает заполненную ячейку (ячейку, содержащую символ 1), и внутренняя память маши­ны находится в состоянии q₁. В процессе работы машина находит справа пустую ячейку, печатает в ней единицу и останавливается. В результате работы машинное слово 01^xq₁1^y00 (где 1ⁿ означает последовательность из п единиц) преобразуется в слово 01^x+yq₀10.

Преобразование, осуществляемое машиной в результате выполнения программы, будем обозначать стрелкой . В данном случае имеем

01^xq₁1^y00 01^x+yq₀100.

Запишем совокупность команд, составляющих данную программу:

q₁1 ® q₁1П — после выполнения у раз этой команды машина придет в состояние 01^x+yq₁00;

q₁0 ® q₀1C — после выполнения этой команды машина приходит в состояние 01^x+yq₀10.

Пример работы машины при х=2, y=4 приведен в табл. 4.1. Состояние машины предоставлено в таблице словом, записанным на ленте с символом внутренней памяти, расположенным над воспринимаемой ячейкой.

Таблица 4.1.

Машина выполняет программу и в том случае, если х=у=0; при этом слово 0q₁00 преобразуется в слово 0q₀10.

Программу машины можно представить в виде таблицы, содержа­щей необходимые команды. Программа рассмотренной машины представлена табл. 4.2., где а — символ обозреваемой ячейки, q — символ состояния внутренней памяти.

Таблица 4.2.

Пример 2.          Машина, уменьшающая данное число на единицу — машина

«-1». Эта машина осуществляет преобразование

01^xq₁1^y001^x+y-2q₀1000 (y>0)

Воспринимая в исходном состоянии заполненную ячейку, машина находит правый край данного массива единиц, стирает единицу и останавливается напротив самой правой из оставшихся единиц. Дополнительное условие, машина «отказывается» работать, если в начальном состоянии она воспринимает незаполненную ячейку.

Команды, осуществляющие данную программу:

q₁1 ® q₂1П — после выполнения команды получаем слово

01^x+1q₂1^y-10;

q₂1 ® q₂1П —после выполнения (у—I) раз этой команды машин приходит в состояние

01^x+yq₂0;

q₂0 ® q₃0Л —это дает слово

01^x+y-1q₃10;

q₃1 ® q₀0Л — после выполнения этой команды имеем заключительное слово

01^x+y-2q₀100.

Программа .данной машины приведена в табл. 4.3.

Таблица 4.3.

В программе отсутствуют команды, начинающиеся словами q₁0 и q₃0. Но ситуация q₃0 вообще не встречается при работе машины, а ситуация q₁0 встречается только в тех случаях, когда данная программа не применима (в этих случаях внутренняя память машины не приходит в заключительное состояние, оставаясь в состоянии q₁).

Пример 3. Машина, сдвигающая головку вправо, на следую­щий массив единиц — машина «С⁺». Необходимо осуществить преобразование    

01^xq₁1^y0^z1^w01^x+y0^z1^w-1q₀ 10 (y0, z1, w1)

(0^z здесь означает последовательность из z нулей). Машина находит следующий справа массив единиц и останавливается, воспринимая самую правую заполненную ячейку.

Программа содержит команды:

q₁1 ® q₁1П  (через у тактов команда дает слово 01^x+yq₁0^z1^v0);

q₁0 ® q₂0П,

q₂0 ® q₂0П (выполнение этих команд приводит к слову 01^x+y0^z q₂1^v0);

q₂1 ® q₃1П,

q₃1 ® q₃1П (получается слово 01^x+y0^z1^vq₃0);

q₃0 ® q₀0Л (получается заключительное слово). Программа приведена в табл. 4.4.

Таблица 4.4.

Если исходное машинное слово имеет вид 01^xq₁1^y00… , то машина продолжает работать «вечно», пристраивая справа пустые ячейки и не приходя в заключительное состояние; таким образом, данная программа не применима к слову 01^xq₁1^y00… .

Будем рассматривать также машины Тьюринга, внутренняя память которых имеет не одно, а несколько заключительных состоянии.

Пример 4. Машина, проверяющая истинность равенства х = 0,— машина «Пр». В исходном положении машина воспринимает самую правую заполненную ячейку массива из х+1 единиц, изображающего на ленте число х. Если слева от этой ячейки — пустая ячейка, то по окончании работы машины ее внутренняя память приходит в состояние q₀₁; если слева — заполненная ячейка, внутренняя память приходит в состояние q₀₂:

01^xq₁1  

Работа машины осуществляется в соответствии со следующей программой (справа от команд будем писать слово, получающееся в результате применения данной команды):

q₁1q₂1Л: 01^x-1q₂110 (или q₂010 при x=0),

q₂1q₀₂1П: 01^xq₀₂10 (или q₂0q₀₁0П: 0q₀₁10).

Программа машины представлена в табл. 4.5.

Таблица 4.5.

Приведем далее без пояснений программы нескольких простых машин.

Пример 5. Машина «С^-», сдвигающая головку влево на следующий массив единиц:

01^x+10^y1^zq₁1^w01^xq₀10^y1^z+w0,

либо, если z = v = 0:

01^x+10^yq₁001^xq₀10^y0

(в последнем случае, в частности, может быть у = 0).

Программа машины приведена в табл. 4.6.

Таблица 4.6.

Пример 6. Машина «H», печатающая число 0:

01^xq₁1^y00001^x+y0q₀10 (x0, y>0);

в частном случае может быть

01^xq₁1^y001^z001^x+yq₀1^z+10

Программа машины приведена в табл. 4.7.

Таблица 4.7.

Пример 7. Машина «Ст», стирающая данный массив единиц:

Программа машины приведена в табл. 4.8.

Таблица 4.8.

Пример 8. Машина «У», удаляющая все нули (кроме одного), расположенные между данным массивом единиц и ближайшим слева.

Построим сначала программу для осуществления следующего цикла:

Как и прежде, слева будем писать команды, а справа — машинные слова, получающиеся в результате применения этих команд столько раз, сколько они применимы:

q₁1 ® q₁1Л — после выполнения этой команды z раз получим слово

Далее,

После выполнения (у—1) циклов исходное машинное слово преобразуется в следующее:

Применение к полученному слову z раз команды q₁1 ® q₁1Л и команды q₁0 ® q₂0Л дает:

Введем команду

Далее имеется команда:

Вводим затем команды

Программа машины «У» приведена в табл. 4.9.

Таблица 4.9.