Машины Тьюринга

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

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

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

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

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

3. Алфавит внутренних состояний {q_0, q₁...q_n}.

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

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

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

a_iq_i ® a_jD_jq_j.

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

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

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

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

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

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

	q1	q2	q3	q4
	lПq2	1Пq2	lЛq4	lСq0
l	-	lЛq3	-	-