Формально об алгоритмах. Вычислительные модели/Задачи/Разрешимость конкатенации — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<latex> Пусть $L_1$ и $L_2$ - разрешимые языки. Является ли разрешимой их конкатенация? То есть $L_1L…»)
 
м
Строка 5: Строка 5:
 
\newline\newline
 
\newline\newline
 
Если язык разрешим, то существует МТ с полубесконечной лентой, разрешающая его: $M_1$ - разрешает $L_1$, $M_2$ - $L_2$.
 
Если язык разрешим, то существует МТ с полубесконечной лентой, разрешающая его: $M_1$ - разрешает $L_1$, $M_2$ - $L_2$.
Тогда конкатенацию будет разрешать следующая МТ с двумя лентами: будем записывать на первую ленту все возможные префиксы слова через пробел по порядку, на вторую - всевозможные суффиксы по порядку, и будем обрабатывать каждое из них по очереди машинами M_1 и M_2(это получится, поскольку они работают с полубесконечной лентов, то есть двигаются в одну сторону, а оставшиеся префиксы/суффиксы находятся другой). Алгоритм работы такой: запускаем на первой ленте M_1, которая при этом недвигается по второй ленте. Если $M_1$ выдала $1$, то запускаем $M_2$: если $1$, то ура мы нашли слово из конкатенации; если одна из них выдаёт $0$, то чистим текущий префикс/суффикс и переходим к следующим. Если мы прочитали всё (словили два пробела подряд), значит слово не принадлежит конкатенации, выводим $0$ и переходим в финальное состояние. То есть мы построили заведомо останавливающуюся машину Тьюринга, значит конкатенация разрешимых языков разрешима.
+
Тогда конкатенацию будет разрешать следующая МТ с двумя лентами: будем записывать на первую ленту все возможные префиксы слова через пробел по порядку, на вторую - всевозможные суффиксы по порядку, и будем обрабатывать каждое из них по очереди машинами $M_1$ и $M_2$(это получится, поскольку они работают с полубесконечной лентов, то есть двигаются в одну сторону, а оставшиеся префиксы/суффиксы находятся другой). Алгоритм работы такой: запускаем на первой ленте M_1, которая при этом недвигается по второй ленте. Если $M_1$ выдала $1$, то запускаем $M_2$: если $1$, то ура мы нашли слово из конкатенации; если одна из них выдаёт $0$, то чистим текущий префикс/суффикс и переходим к следующим. Если мы прочитали всё (словили два пробела подряд), значит слово не принадлежит конкатенации, выводим $0$ и переходим в финальное состояние. То есть мы построили заведомо останавливающуюся машину Тьюринга, значит конкатенация разрешимых языков разрешима.
  
 
P.S. Если фантазировать дальше, то можно задать вопрос: является ли конкатенация P языков P языком ит.д. В принципе идея та же самая: если машина Тьюринга работает за полином, значит эквивалентная ей машина с полубесконечной лентой тоже работает за полином(пути увеличиваются в два раза). У слова n префиксов и суффиксов, значит мы каждую машину запустим n раз, то есть все равно получим в итоге машину, которая работает за полином.
 
P.S. Если фантазировать дальше, то можно задать вопрос: является ли конкатенация P языков P языком ит.д. В принципе идея та же самая: если машина Тьюринга работает за полином, значит эквивалентная ей машина с полубесконечной лентой тоже работает за полином(пути увеличиваются в два раза). У слова n префиксов и суффиксов, значит мы каждую машину запустим n раз, то есть все равно получим в итоге машину, которая работает за полином.

Версия 09:25, 17 мая 2015