Я читаю Sipser , и я нахожу , что это трудно понять , что этот процесс таким образом, что , если вы дадите мне K машины Тьюринга с к лентам, я могу выплюнуть эквивалентную машину Тьюринга только с одной лентой. Пример был бы хорош. На самом деле, отработанный пример , который показывает , как перейти от ТМА , который имеет ленту на один , который имеет 1 ленту , что я действительно искал. Я не смог найти один до сих пор. Я также не ищу какие - либо доказательства.
turing-machines
simulation
user678392
источник
источник
Ответы:
Ответ бесстыдно скопировал с себя :
Многоленточная машина Тьюринга по большей части такая же, как и одноленточная машина, за исключением того, что у нас есть расширенная функция перехода где k - количество лент. Таким образом, в каждом состоянии функция перехода считывает содержимое каждой ленты, переходит в новое состояние, (возможно) записывает что-то на каждую ленту и перемещает каждую головку - так же, как обычный TM, за исключением того, что теперь у нас есть больше вещей для чтения, записи и двигаться.Q × ΓК→ Q × ΓК× { L , R }К К
Как показывает ваш вопрос, такую машину можно смоделировать с помощью однотонной ТМ. Более того, это можно сделать только с помощью квадратичного замедления (поэтому для полиномиально закрытых классов достаточно поговорить об одноленточных машинах).
Доказательство этому несколько сложное и легко доступное с помощью простого веб-поиска, поэтому я просто нарисую раскладку клавиш на одну ленту.К
Основная идея довольно проста; мы просто добавляем несколько новых символов и отслеживаем каждую ленту и возглавляем одну за другой. На каждом этапе вычислений мы могли посетить только ограниченное количество любых лент, поэтому нам нужно только хранить столько информации о каждой ленте. Таким образом, для каждого мы добавляем новый символ γ _ к Γ, который будет указывать, где находится головка (для каждой ленты) в любой точке вычисления. Мы также вводим символ-разделитель # для Γ, который будет указывать начало и конец «виртуальных» лент. Заданный вход ω = ω 1 … ω nγ∈ Γ γ-- Γ # Γ ω=ω1…ωn (мы можем предположить, что даже на многолентовой машине все входные данные находятся на первой ленте - доказательство того, почему это хорошее упражнение) на многоленточной машине наша одноленточная машина будет иметь ввод
(Надеюсь) простой пример:
Чтобы создать комбинированную одноленточную машину, нам нужно добавить новые символы в ленточный алфавит:
После второго шага:
Конечно, это высокоуровневое представление процесса - я не пытался объяснить, как создавать состояния, или как каждая моделируемая лента становится длиннее (для этого вам понадобится небольшая процедура, которая проверяет, сталкивались ли вы с конец смоделированной ленты, затем перемещает все вправо на один шаг вперед и сжимает новый пробел - т.е. он добавляет только смоделированные ячейки ленты, когда они необходимы).
источник