У меня есть вопрос: рассмотрим машину Тьюринга Cw, которая стирает ввод, записывает w на ленту и останавливается при сканировании крайнего левого символа w. Дизайн машины Тьюринга C011
Мне нужно объяснение, в чем актуален вопрос и что делает Cw. Я как бы понимаю, что он пишет пустой символ на каждом вводе, но остальное мне непонятно. Надеюсь, кто-нибудь поможет мне разобраться в вопросе и в том, что от меня требуется.
В вашем случае w = 011.
Действительно, TM сначала должен перезаписать весь ввод. Думаю, можно предположить, что во вводе нет пробелов. Таким образом, как только TM прочитает пустое место на входной ленте, он должен начать запись 011.
При записи второй 1 войдите в состояние, для которого не существует никаких переходов. Таким образом вы обеспечите остановку машины в этом положении. Ничего не сказано явно о том, следует ли это состояние принимать, но было бы разумно иметь его как уникальное принимающее состояние.
