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

1. Лента, разбитая на клетки, неограниченная слева и справа.

2. Все клетки пусты (содержат символ S₀), кроме конечного их числа (могут содержаться символы: S₁,S₂,...,S_n).

3. Машина может находиться в одном из m состояний (q₁,q₂,...q_m).

4. Каждая инструкция предписывает, что нужно делать в состоянии j, если в считываемой клетке символ S_i.

(Остановиться, сдвинуться влево, сдвинуться вправо, записать в клетку символ S_i (i=0,...,n)).

Машина Тьюринга представляет собой набор инструкций. Каждая инструкция содержит четверку данных:

<текущее состояние, считываемый символ, действие, новое состояние>.

Если для текущего состояния и считываемого символа не предусмотрена инструкция, то машина останавливается.

Пример:

Лента пуста. Поместить три символа S₁.

q1,S0,S1,q1; q1,S1,L,q2; q2,S0,S1,q2, q2,S1,L,q3; q3,S0,S1,q3.

Более сложный пример:

Удвоение числа единиц. Обозначим: 0 - пусто, 1 - единственный символ. На ленте несколько единиц подряд. Головка чтения устройства установлена на самую левую единицу. Нужно получить удвоенную последовательность единиц и поместить головку чтения в самую левую позицию массива.

1. q1,1,L,q2 - из начального состояния влево

2. q2,0,L,q3 - видим 0 и идем еще влево

3. q3,0,1,q3 - там тоже 0, меняем его на 1

4. q3,1,L,q4 - видим 1, идем влево

5. q4,0,1,q4 - там тоже 0, меняем на 1

6. q4,1,R,q5 - итак, нарисовали две единицы и уходим вправо

7. q5,1,R,q5 - цикл - смещаемся вправо до 0

8. q5,0,R,q6 - нашли 0 (это разделитель между новым и старым множествами единиц), идем вправо

9. q6,1,R,q6 - цикл - смещаемся вправо до 0

10. q6,0,L,q7 - нашли правый край исходного множества единиц, смещаемся влево

11. q7,1,0,q7 - стираем одну единицу

12. q7,0,L,q8 - и смещаемся влево

13. q8,1,L,q9 - есть еще единицы в исходном множестве, смещаемся влево. Следующая инструкция 15.

14. q8,0,L,q11 - исходное множество единиц исчерпано, переходим на новое множество. Следующая инструкция 20.

15. q9,1,L,q9 - пробегаем все оставшиеся единицы старого множества

16. q9,0,L,q10 - нашли конец, перешли на новое множество

17. q10,1,L,q10 - пробежали все единицы нового множества

18. q10,0,R,q2 - нашли конец, вернулись на последнюю 1

19. q2,1,L,q3 - возникло состояние дописывания двух единиц слева ...Идем к инструкции 3.

20. q11,1,L,q11 - шагаем по новому множеству до конца

21. q11,0,R,q12 - наехали на первый 0 после множества, вернулись. Для состояния 12 нет инструкции. Останов.

Множество машин Тьюринга счетно!

Каждая машина Тьюринга на {0,1} задает некоторую функцию, аргументом которой является число единиц начального состояния, значением - число единиц конечного состояния, если оно достигнуто, в противном случае значение не определено.