Машина Тьюринга ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ

Question

Машина Тьюринга ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ

Влад Ковалев Ученик (104), закрыт 3 недели назад

ПОМОГИТЕ ПОЖАЛУЙСТА, нужно написать таблицу для машины Тьюринга с алфавитом 1λ, такую, что слово : 11λ111λ11, а Результат должен быть: y+3+z = 3+3+2 = 8 единиц после обработки.
Вот пример таблицы, но он неправильный и сама машина должна возвращаться в самый левый символ после работы:

Сама функция:
f(x,y,z) = y+3+z

Дополнен 1 месяц назад

нужно это для эмулятора машины тьюринга

Answer 1

Стоим над самым левым символом.

 1 q0 -> λ R q0
λ q0 -> 1 R q1
1 q1 -> 1 R q1
λ q1 -> 1 L q2
1 q2 -> 1 L q2
λ q2 -> 1 N !

q0:
Движемся вправо, стирая все единицы первого слова.
Когда доходим до λ между первым и вторым словом, ставим 1 (+1) и переходим в q1.

q1:
Пока в текущей ячейке 1, движемся вправо.
Когда доходим до λ между вторым и третьим словом, ставим 1 (+1) и переходим в q2.

q2:
Пока в текущей ячейке 1, движемся влево.
Когда доходим до λ слева от объединённого слова, ставим 1 (+1) и заканчиваем работу с кареткой над этой ячейкой.