Он-лайн симуляция двухголовочной ленты машины Тьюринга с использованием одноголовочной ленты

Question

У меня есть вопрос, и я еще не смог найти ответ. Мне нужно провести онлайн-симуляцию двухголовочной ленты машины Тьюринга с использованием одноголовочной ленты. Я нашел несколько статей в Интернете о том, что одной ленты с одной головкой недостаточно для этой проблемы, и симуляция должна выполняться с использованием двух лент с одной головкой, но я не смог представить точную симуляцию двух голова ТМ с использованием этих одноголовочных лент. Есть какие-нибудь мысли о том, как это сделать? Спасибо,

Answer 1

Вот один из возможных способов сделать это:

1. Начните с мультитрековой машины Тьюринга. Если вы не видели этого раньше, это TM, в котором каждая ячейка ленты сегментирована на несколько разных строк, каждая из которых может содержать независимый символ. Это эквивалентно обычной машине Тьюринга, потому что в ячейке ленты может храниться только конечное число возможных комбинаций символов, поэтому вы можете создать свой алфавит ленты, который будет иметь разные символы для каждого.

2. Пусть верхняя дорожка удерживает ваш ввод, а нижняя дорожка хранит места расположения головок магнитных лент (либо пометив пустым "ничего"," 1" для магнитной головки 1 здесь," 2" для магнитной головки 2 здесь ", и 3 для "обе ленты ленты здесь."

3. Чтобы смоделировать один шаг, отсканируйте вход и найдите маркеры. Каждый раз, когда вы это делаете, вы можете хранить в своем контроле с конечным состоянием, какие символы находятся под этими головками ленты. Есть только конечно много возможностей. Затем отсканируйте ленту и смоделируйте перемещение головок ленты соответствующим образом.

Надеюсь это поможет!