Лекция: Машины Тьюринга

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

Но машина Тьюринга – это все-таки прежде всего метод математического моделирования.

Машина Тьюринга включает:

1. Потенциально бесконечную (вправо) ленту, разделенную на ячейки.

2. Считывающе-записывающую головку с устройством управления (УУ).

3. Алфавит внутренних состояний {q0, q1...qn}.

4. Входной-выходной алфавит.

Определяется начальная конфигурация. Головка смотрит на какую-то ячейку и устройство управления находится в начальном состоянии q1.

Устройство управления на основании считанного из ячейки символа и внутреннего состояния пишет в ячейку символ (возможно, тот же самый), совершает действие D и переходит в новое внутреннее состояние (возможно прежнее). Это и есть команда Машины Тьюринга, которую можно записать так:

aiqi ® ajDjqj.

D = {Л, П, С} — множество действий.

Л – влево, П – вправо, С — стоять.

Совокупность команд составляет программу машины Тьюринга, которая обычно оформляется в виде таблицы.

Машина заканчивает работу, когда переходит в состояние q0.

l — пустой символ.

Пример: Построим машину Т, которая в сплошной последовательности 1 стирает первую и две последние. (l — пустой символ).