Условие:
На ленту подряд вписаны два конечных набора единиц, разделенные звездочкой. Составьте программу машины Тьюринга, которая выписывала бы подряд (без разделения звездочкой) столько единиц, сколько их в обоих наборах (сложение единиц).
Решение:
Наша цель – написать программу для машины Тьюринга, которая на вход получает ленту вида
111…1 * 111…1
то есть два непрерывных набора единиц, разделённых символом «», и должна оставить на ленте только единицы, число которых равно сумме единиц в первом и втором наборе (то есть результат должен быть 111…1, где количество единиц – сумма исходных).
Один из способов решения – удалить символ «» путём сдвига всех символов правее него на одну позицию влево. Тогда лента примет вид
111…1 111…1
то есть именно два набора, записанные подряд, что и есть сумма.
Мы разработаем программу машины Тьюринга, которая действует следующим образом:
- В начальном состоянии q0 машина движется вправо, пока не встретит символ «*...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи