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

<latex>
Пусть $L_1$ и $L_2$ - разрешимые языки. Является ли разрешимой их конкатенация? То есть $L_1L_2 = \{ab \;|\; a \in L_1, b \in L_2\}$
\newline\newline
Решение:
\newline\newline
Если язык разрешим, то существует МТ с полубесконечной лентой, разрешающая его: $M_1$ - разрешает $L_1$, $M_2$ - $L_2$.
Тогда конкатенацию будет разрешать следующая МТ с двумя лентами: будем записывать на первую ленту все возможные префиксы слова через пробел по порядку, на вторую - всевозможные суффиксы по порядку, и будем обрабатывать каждое из них по очереди машинами $M_1$ и $M_2$(это получится, поскольку они работают с полубесконечной лентов, то есть двигаются в одну сторону, а оставшиеся префиксы/суффиксы находятся другой). Алгоритм работы такой: запускаем на первой ленте M_1, которая при этом недвигается по второй ленте. Если $M_1$ выдала $1$, то запускаем $M_2$: если $1$, то ура мы нашли слово из конкатенации; если одна из них выдаёт $0$, то чистим текущий префикс/суффикс и переходим к следующим. Если мы прочитали всё (словили два пробела подряд), значит слово не принадлежит конкатенации, выводим $0$ и переходим в финальное состояние. То есть мы построили заведомо останавливающуюся машину Тьюринга, значит конкатенация разрешимых языков разрешима.

P.S. Если фантазировать дальше, то можно задать вопрос: является ли конкатенация P языков P языком ит.д. В принципе идея та же самая: если машина Тьюринга работает за полином, значит эквивалентная ей машина с полубесконечной лентой тоже работает за полином(пути увеличиваются в два раза). У слова n префиксов и суффиксов, значит мы каждую машину запустим n раз, то есть все равно получим в итоге машину, которая работает за полином.
</latex>

[[Категория:Предложенные студентами задачи]]