Примеры неразрешимых задач: задача о выводе в полусистеме Туэ — различия между версиями
Gr1n (обсуждение | вклад) |
Gr1n (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition = | |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>. | ||
}} | }} |
Версия 23:20, 13 января 2014
Определение: |
Полусистема Туэ (semi-Thue system) - это формальная система, определяемая алфавитом | и конечным множеством подстановок вида , где - слова из .
Подстановка интерпретируется как правило вывода следующим образом:
по , если слово получается путем подстановки какого-нибудь вместо какого-то вхождения в .
Вывод
из - цепочка , где каждое получается из некоторой подстановкой.
Определение: |
Проблема останова (halting problem) - это задача, в которой требуется по заданной программе проверить завершиться ли она на определенных входных данных. |
Теорема: |
Проблема останова неразрешима. |
Доказательство: |
Доказательство теоремы приведено в примере использования теоремы о рекурсии. |
Источники
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера