Чтобы построить машину Тьюринга, которая вычисляет функцию f(x), определенную как:

• f(x) = 1, если x = 0
• f(x) = 0, если x ≠ 0

и при этом головка находится справа, мы можем следовать следующим шагам:

1. Определим алфавит: В нашем случае алфавит A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Λ}, где Λ обозначает пустую ячейку.
2. Определим состояния машины:
   • q0 - начальное состояние
   • q1 - состояние, когда мы нашли 0
   • q2 - состояние, когда мы нашли любой другой символ (от 1 до 9)
   • q_accept - состояние принятия (выход 1)
   • q_reject - состояние отказа (выход 0)
3. Определим переходы:
   • В состоянии q0:
     • Если читаем 0, переходим в состояние q1, записываем 1 и движемся влево.
     • Если читаем любой другой символ (1-9), переходим в состояние q2, записываем 0 и движемся влево.
     • Если читаем Λ (пустую ячейку), остаемся в этом состоянии и переходим в состояние q_reject.
   • В состоянии q1:
     • Если читаем 0, остаемся в состоянии q1 и движемся влево.
     • Если читаем Λ, переходим в состояние q_accept и записываем 1.
     • Если читаем любой другой символ, переходим в состояние q_reject.
   • В состоянии q2:
     • Если читаем 0, переходим в состояние q_reject.
     • Если читаем любой другой символ (1-9), остаемся в состоянии q2 и движемся влево.
     • Если читаем Λ, переходим в состояние q_reject.
4. Определим конечные состояния:
   • q_accept - вывод 1 (функция f(x) = 1)
   • q_reject - вывод 0 (функция f(x) = 0)

Таким образом, машина Тьюринга будет проверять входное значение, начиная с правой стороны, и в зависимости от найденного символа будет переходить в соответствующее состояние, выдавая результат в конечном состоянии.