Универсальная кодировка машины Тьюринга

Построим универсальную кодировку программы машины Тьюринга M. Для этого занумеруем алфавит {a0, a1, , ak }, со-

стояния {q0, q1, , qn} и сдвиги натуральными числами:

R	L	S	a0	a1		ak	q0	q1		qn
1	3	5	7	9		2k+1	0	2		2n

Тогда любую команду можно закодировать набором из 5 чисел, а этот набор представить на ленте с помощью алфавита

{1, } стандартным образом, помещая вместо разделяющих ну-

лей символ . При этом мы получим код команды, который обозначим через K .

Теперь можно составить код всей программы

K(M ) =K1 K2 K p ,

где Ki — коды всех команд программы. Отметим, что по коду всегда можно восстановить программу.

Пример

Построить код машины Тьюринга с программой:

q11 → q11R , q10 → q21L, q21 → q21L, q20 → q00R .

Решение. Закодируем набором из 5 чисел каждую команду, используя таблицу кодов:

2 9 2 9 1, 2 7 4 9 3, 4 9 4 9 3, 4 7 0 7 1.

69