Имитация недетерминированной машины Тьюринга с детерминированной машиной Тьюринга [JFLAP]

Question

Проблема: Учитывая начальное состояние q0 и полностью пустую ленту, за исключением одного квадрата с символом #, найдите # и остановитесь на нем.

Недетерминированно:

Эта машина выбирает поиск влево или вправо от начального состояния и продолжает движение в этом направлении до следующего символа #, где он остается.

Детерминистически:

Как мне воспроизвести эту машину в детерминированной форме? Я провел некоторое исследование, и кажется, что эту проблему можно решить, обращаясь к обеим возможностям / ветвям "дерева", но я не могу соединить точки здесь...

Answer 1

Вы не просто пробегаете не # ячейки, а отмечаете их как посещенные. Далее вы делаете две ветви одновременно, чередуя их.

1. Пометьте текущую ячейку знаком "+" (если это не # уже)
2. Бегите направо, пока вы видите +. Когда вы увидите первый пробел, отметьте его +.
3. Бегите налево, пока вы видите +. Когда вы увидите первый пробел, отметьте его +. Перейти к 2.

Таким образом, вы можете обрабатывать любое фиксированное количество недетерминированных ветвей детерминированным способом. Конечно, бег вокруг занимает гораздо больше времени, чем фактическое моделирование.