Как сопоставить ленты с «К-ленты» машины Тьюринга в одной ленте «1-ленты» машины Тьюринга

11

Я читаю Sipser , и я нахожу , что это трудно понять , что этот процесс таким образом, что , если вы дадите мне K машины Тьюринга с к лентам, я могу выплюнуть эквивалентную машину Тьюринга только с одной лентой. Пример был бы хорош. На самом деле, отработанный пример , который показывает , как перейти от ТМА , который имеет ленту на один , который имеет 1 ленту , что я действительно искал. Я не смог найти один до сих пор. Я также не ищу какие - либо доказательства.k

user678392
источник
Что вы подразумеваете под "эквивалентной машиной"? Каков вход и каков выход? (Возможно, вы имели в виду одну машину Тьюринга с лентами?)k
Yuval Filmus
Да. Один токарный станок с k лентами.
user678392 26.09.13

Ответы:

17

Ответ бесстыдно скопировал с себя :

Многоленточная машина Тьюринга по большей части такая же, как и одноленточная машина, за исключением того, что у нас есть расширенная функция перехода где k - количество лент. Таким образом, в каждом состоянии функция перехода считывает содержимое каждой ленты, переходит в новое состояние, (возможно) записывает что-то на каждую ленту и перемещает каждую головку - так же, как обычный TM, за исключением того, что теперь у нас есть больше вещей для чтения, записи и двигаться.Q×ΓkQ×Γk×{L,R}kk

Как показывает ваш вопрос, такую ​​машину можно смоделировать с помощью однотонной ТМ. Более того, это можно сделать только с помощью квадратичного замедления (поэтому для полиномиально закрытых классов достаточно поговорить об одноленточных машинах).

Доказательство этому несколько сложное и легко доступное с помощью простого веб-поиска, поэтому я просто нарисую раскладку клавиш на одну ленту.k

Основная идея довольно проста; мы просто добавляем несколько новых символов и отслеживаем каждую ленту и возглавляем одну за другой. На каждом этапе вычислений мы могли посетить только ограниченное количество любых лент, поэтому нам нужно только хранить столько информации о каждой ленте. Таким образом, для каждого мы добавляем новый символ γ _ к Γ, который будет указывать, где находится головка (для каждой ленты) в любой точке вычисления. Мы также вводим символ-разделитель # для Γ, который будет указывать начало и конец «виртуальных» лент. Заданный вход ω = ω 1ω nγΓγ_Γ#Γω=ω1ωn(мы можем предположить, что даже на многолентовой машине все входные данные находятся на первой ленте - доказательство того, почему это хорошее упражнение) на многоленточной машине наша одноленточная машина будет иметь ввод

#ω1_ωn#_#_##_#k sections, one per tape

k

(Надеюсь) простой пример:

Σ={0,1}Γ={0,1,}ω=10101

Tape 1:10101Tape 2:Tape 3:

Чтобы создать комбинированную одноленточную машину, нам нужно добавить новые символы в ленточный алфавит:

  1. Нам нужен символ, который будет обозначать начало и конец моделируемых лент
  2. Γ

Γ={0,1,,0_,1_,_,#}

#1_0101#_#_#
) и смоделированные головки из 3 смоделированных лент (подчеркнутые символы). Конечно, лента как обычно простирается бесконечно вправо. Я также слегка обманул, переместив головку ленты к первому символу в первой строке; строго он должен начинаться с самой левой ячейки, но это тривиальная техническая задача.

#

1101

1

Tape 1:10101Tape 2:1Tape 3:

0

Tape 1:10101Tape 2:1Tape 3:1

Γ

#10_101#1_#_#

После второго шага:

#101_01#1_#1_#

Конечно, это высокоуровневое представление процесса - я не пытался объяснить, как создавать состояния, или как каждая моделируемая лента становится длиннее (для этого вам понадобится небольшая процедура, которая проверяет, сталкивались ли вы с конец смоделированной ленты, затем перемещает все вправо на один шаг вперед и сжимает новый пробел - т.е. он добавляет только смоделированные ячейки ленты, когда они необходимы).

Люк Мэтисон
источник
2
В качестве альтернативы, используйте отдельные « дорожки » для записи отдельных лент рядом друг с другом в одном и том же месте. Это, однако, предполагает введение нового алфавита.
Хендрик Ян
2
@ user678392 Детальная проработка конструкции и написание всего этого заняло бы, по крайней мере, пару часов. Если вы даже не собираетесь объяснять, какую часть вы не понимаете, зачем кому-то вкладывать столько работы от вашего имени? А что если кто-нибудь сделает? Вы просто собираетесь сказать: «Я не понимаю этого. Кто-то другой делает это»?
Дэвид Ричерби
1
@ user678392 Спасибо. И, просто чтобы уточнить, с какими трудностями вы сталкиваетесь по-английски (т. Е. Перефразирует, вероятно, поможет) или вам нужно больше подробностей в объяснении?
Дэвид Ричерби
1
@ user678392, я добавил пример зрения высокого уровня первых шагов преобразования и практический вывод на ленте (ов). Я избегал обсуждать, как построить новый набор состояний, так как это очень сложно, и вы не получите лучшего объяснения, чем то, что в Sipser или аналогичном - это по своей природе просто и математично.
Люк Мэтисон
1
@RomaKarageorgievich Похоже, что за последние 5 лет ряд более ясных доказательств исчез (не верьте Интернету: D). Самое ясное, что я нашел здесь (предупреждение, файл .doc!). Доказательство Мартина «Введение в языки и теорию вычислений» весьма неплохо, если у вас есть доступ к этой книге (стр. 244 в 4-м издании). Доказательство в «Введение в теорию вычислений» Сипсера достаточно (стр. 177 в 3-м изд.).
Люк Мэтисон