Показывая, что набор TMS, которые дважды посещают начало

Question

Я пытаюсь доказать это

$ L_1 = { langle m rangle mid m text {это машина Turing и посещает} Q_0 Text {не реже двух раз} varepsilon } notin r $.

Я не уверен, уменьшить ли проблему остановки или нет. Я попытался построить новую машину $ m '$ для $ ( langer m rangle, w) $, так что $ m' $ посещает $ q_0 $ дважды, если я остановился на $ w $. Это конкретный $ Q_0 $, данный мне, но я не пришел на умную конструкцию, что дало бы запрошенную. Может быть, легче показать, что это $ re $, а не $ core $? Очевидно, что он находится в $ re $, и мне нужно показать, что $ l_2^{c} $ не в $ re $.

Что я должен делать?

Answer 1

Не делайте это сложнее, чем есть. Вместо того, чтобы дать вам полные решения, я дам вам частичное решение, которое должно позволить вам выработать детали самостоятельно:

Каждый ТМ превращается в ТМ, который посещает его начальное состояние ровно один раз. Для этого введите новое состояние $ Q^'_ 0 $, которое будет новым начальным состоянием. Затем добавьте $ varepsilon $ -Transition от $ Q^'_ 0 $ в $ Q_0 $. Это единственный способ «оставить» государство $ Q'_0 $.

Для этой модифицированной машины принимающий прогон посещает начальное состояние один раз и заканчивается в состоянии принятия. Что осталось сделать, так это изменить машину дальше, так что она возвращается к $ q^'_ 0 $, после того, как машина была в состоянии принятия. Но вы должны убедиться, что когда $ q^'_ 0 $ посещается во второй раз, вы перейдете к новому принятому состоянию. Но не сложно записать, как часто вы посещали штат.

Если вы хотите, чтобы другое состояние посещалось дважды, то вначале вы всегда можете сделать обходной путь, который посещает это состояние (вы записываете, что машина находится в режиме «Обход», чтобы написать флаг на специальной ленте). Чем вы перенаправляете обычные вычисления, так что, если оно посещает запрошенное состояние, он посещает копию этого состояния. Наконец, при принятии вы возвращаетесь в запрошенное состояние. Концептуально, это не сильно отличается от перераспределения государств.