Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

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

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

Сама функция:
f(x,y,z) = y+3+z
Дополнен 1 месяц назад
нужно это для эмулятора машины тьюринга
Лучший ответ
Андрей Высший разум (469129) 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) и заканчиваем работу с кареткой над этой ячейкой.
Влад КовалевУченик (104) 1 месяц назад
а как это вписать сюда?
Андрей Высший разум (469129) Влад Ковалев, Так и вписывать. У меня слева от -> координаты ячейки, справа - команда в ячейке. А как именно прописывать конкретные команды в конкретной машине - это же тебе должны были на занятиях объяснять. Все команды, кроме последней, проблем не создают. А вот как написать команду последнюю команду "поставить 1, не сдвигать каретку и завершить работу" - это тебе виднее.
Влад КовалевУченик (104) 1 месяц назад
Просто мне бы написать конкретно для этого эмулятора, там обязательно в каждом шаге прописывать направление, R - право, L -влево, N -остаёмся на месте, ! - стоп машина
Влад КовалевУченик (104) 1 месяц назад
Вот сам интерфейс
Остальные ответы
Похожие вопросы