Примеры машин Тьюринга.

Опишем несколько простых (элементарных) машин Тьюринга. Элементарные машины — это машины с алфавитом {s₀, |}, получаемым присоединением к однобуквенному алфавиту {|} пустой буквы s₀. Результатом их применения к записи на ленте являются некоторые элементарные изменения (преобразования) этой записи.

Пример 1.

Машина А, имеющая программу, данную в таблице 5, выше уже рассмотрена.

Таблица 5

A	s0	|
q1	|Нq0	|Пq1

Пример 2.

Машина B воспринимает любое число из набора x₁, x₂,..., x_n, уменьшает число палочек в его записи на одну и останавливается, воспринимая уменьшенное число. Так работает машина с программой, данной в таблице 6.

Таблица 6

B	s0	|
q1		s0Лq0

Задача 2.

Изобразите на ленте в алфавите {s₀, |} набор чисел 2, 3, 4 и пусть машина В воспринимает второе число в стандартном положении. Изобразите ленту после работы машины. Какой набор чисел будет записан на ней?

Пример 3.

Машина C воспринимает набор чисел x₁, x₂,..., x_n в стандартном положении и через одну пустую ячейку справа от этого набора записывает число 0, после чего останавливается, воспринимая 0.

Программа машины C представлена таблицей 7.

Таблица 7

C	s0	|
q1	s0Пq2	|Пq1
q2	|Нq0

Пустая клетка таблицы означает, что пара (|, q₂) не возникает в процессе работы этой машины (поэтому можно записать в этой клетке произвольную команду).