Формально об алгоритмах. Вычислительные модели/Задачи/Разрешимость конкатенации — различия между версиями
Материал из 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