Примеры неразрешимых задач: задача о выводе в полусистеме Туэ — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 4 промежуточные версии 3 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition = '''Полусистема Туэ''' (англ. ''semi-Thue system'') {{---}} это формальная система, определяемая алфавитом <tex>A</tex> | + | |definition = '''Полусистема Туэ''' ('''ассоциативное исчисление''') (англ. ''semi-Thue system'') {{---}} это формальная система, определяемая алфавитом <tex>A</tex> |
и конечным множеством подстановок вида <tex>\alpha_i\rightarrow \beta_i</tex>, где <tex>\alpha_i, \beta_i</tex> — слова из <tex>A</tex>. | и конечным множеством подстановок вида <tex>\alpha_i\rightarrow \beta_i</tex>, где <tex>\alpha_i, \beta_i</tex> — слова из <tex>A</tex>. | ||
}} | }} | ||
Строка 7: | Строка 7: | ||
<tex>\gamma \vDash \delta</tex> по <tex>R_i</tex> , если слово <tex>\delta</tex> получается путем подстановки <tex>\beta_i</tex> вместо какого-то вхождения <tex>\alpha_i</tex> в <tex>\gamma</tex>. | <tex>\gamma \vDash \delta</tex> по <tex>R_i</tex> , если слово <tex>\delta</tex> получается путем подстановки <tex>\beta_i</tex> вместо какого-то вхождения <tex>\alpha_i</tex> в <tex>\gamma</tex>. | ||
− | Вывод <tex>\beta</tex> из <tex>\alpha</tex> — цепочка <tex>\alpha\vDash\epsilon_1\vDash\epsilon_2\vDash | + | Вывод <tex>\beta</tex> из <tex>\alpha</tex> — цепочка <tex>\alpha\vDash\epsilon_1\vDash\epsilon_2\vDash \ldots \vdash\beta</tex>, где каждое <tex>\epsilon_j</tex> получается из <tex>\epsilon_{j-1}</tex> некоторой подстановкой. |
{{Теорема | {{Теорема | ||
Строка 35: | Строка 35: | ||
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* q_n </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима. | Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* q_n </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима. | ||
}} | }} | ||
+ | |||
+ | == См. также == | ||
+ | * [[m-сводимость]] | ||
+ | * [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]] | ||
+ | * [[Примеры неразрешимых задач: задача о замощении | Задача о замощении]] | ||
+ | * [[Неразрешимость исчисления предикатов первого порядка]] | ||
==Примечания== | ==Примечания== |
Текущая версия на 19:33, 4 сентября 2022
Определение: |
Полусистема Туэ (ассоциативное исчисление) (англ. semi-Thue system) — это формальная система, определяемая алфавитом | и конечным множеством подстановок вида , где — слова из .
Подстановка интерпретируется как правило вывода следующим образом:
по , если слово получается путем подстановки вместо какого-то вхождения в .
Вывод
из — цепочка , где каждое получается из некоторой подстановкой.Теорема: |
В полусистеме Туэ задача вывода из слова слово (англ. word problem for semi-Thue systems) неразрешима. |
Доказательство: |
Сведем неразрешимую задачу проблемы останова[1] к нашей. Для этого построим по структуре данной из проблемы останова МТ полусистему Туэ. Пусть — стартовое состояние, — допускающее состояние МТ. Для построение искомой полусистемы будем описывать текущее состояние МТ с помощью строки , где — текущее состояние автомата, — строка, записанная на ленте, и — маркера начала и конца строки соответственно. Пусть — последний символ строки , а — первый символ строки . При этом головка указывает на символ . Тогда текущий шаг МТ можно описать с помощью следующих преобразований строк:
В силу конечности множеств состояний автомата ( ) и алфавита ( ) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркеров (прим. B — пустой символ ленты) :и для И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние , получить уникальное слово. Это необходимо, чтобы мы смогли построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. При этом пусть это уникальное состоит лишь из символа допускающего состояния . Таким образом, имеем следующие правила:Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове и для , если в построенной полусистеме . Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима. |
См. также
- m-сводимость
- Проблема соответствий Поста
- Задача о замощении
- Неразрешимость исчисления предикатов первого порядка
Примечания
- ↑ Пример использования теоремы о рекурсии