Представление машины Тьюринга таблицей соответствия

Представление машины Тьюринга таблицей соответствия

Пример 1.

• Построить машину Тьюринга, которая правильно вычисляет функцию f(x) =x+1 по правилам двоичного сложения.
• Решение. Исходя из формулировки задачи, требующей вычислить функцию по правилам сложения в двоичной системе сложения, выберем входной алфавит: А ={0, 1, ε}.
• Представим машины Тьюринга таблицей соответствия и графом. Таблица соответствия:

• Запишем программу построенной машины Тьюринга для случая, когда входная цепочка на ленте равна двоичному числу 111. Слева от каждой команды приведем представление входной цепочки на ленте до выполнения данной команды. Символ, который находится под головкой, будем помечать подчеркиванием.
• 1) q01 → q01R ε111ε 6) q11 → q10L ε110ε

• 2) q01 → q01R ε111ε 7) q11 → q10L ε100ε
• 3) q01 → q01R ε111ε 8) q1ε → q21L ε000ε
• 4) q0ε → q1εL ε111ε 9) q2 ε → qz εR ε1000ε
• 5) q11 → q10L ε111ε