Примеры машин Тьюринга.
Опишем несколько простых (элементарных) машин Тьюринга. Элементарные машины — это машины с алфавитом {s0, |}, получаемым присоединением к однобуквенному алфавиту {|} пустой буквы s0. Результатом их применения к записи на ленте являются некоторые элементарные изменения (преобразования) этой записи. Пример 1. Машина А, имеющая программу, данную в таблице 5, выше уже рассмотрена. Таблица 5
Пример 2. Машина B воспринимает любое число из набора x1, x2,..., xn, уменьшает число палочек в его записи на одну и останавливается, воспринимая уменьшенное число. Так работает машина с программой, данной в таблице 6. Таблица 6
Задача 2. Изобразите на ленте в алфавите {s0, |} набор чисел 2, 3, 4 и пусть машина В воспринимает второе число в стандартном положении. Изобразите ленту после работы машины. Какой набор чисел будет записан на ней? Пример 3. Машина C воспринимает набор чисел x1, x2,..., xn в стандартном положении и через одну пустую ячейку справа от этого набора записывает число 0, после чего останавливается, воспринимая 0. Программа машины C представлена таблицей 7. Таблица 7
Пустая клетка таблицы означает, что пара (|, q2) не возникает в процессе работы этой машины (поэтому можно записать в этой клетке произвольную команду).
|
