Примеры неразрешимых задач: задача о выводе в полусистеме Туэ

Определение:

Полусистема Туэ (semi-Thue system) - это формальная система, определяемая алфавитом [math]A[/math] и конечным множеством подстановок вида [math]\alpha_i\rightarrow \beta_i[/math], где [math]\alpha_i, \beta_i[/math] - слова из [math]A[/math].

Подстановка [math]\alpha_i\rightarrow \beta_i[/math] интерпретируется как правило вывода [math]R_i[/math] следующим образом: [math]\gamma \vDash \delta[/math] по [math]R_i[/math] , если слово [math]\delta[/math] получается путем подстановки какого-нибудь [math]\beta_i[/math] вместо какого-то вхождения [math]\alpha_i[/math] в [math]\gamma[/math].

Вывод [math]\beta[/math] из [math]\alpha[/math] - цепочка [math]\alpha\vDash\epsilon_1\vDash\epsilon_2\vDash .. \vdash\beta[/math], где каждое [math]\epsilon_j[/math] получается из [math]\epsilon_{j-1}[/math] некоторой подстановкой.

Определение:

Проблема останова (halting problem) - это задача, в которой требуется по заданной программе проверить завершиться ли она на определенных входных данных.

Теорема:

Проблема останова неразрешима.

Доказательство:

[math]\triangleright[/math]

Доказательство теоремы приведено в примере использования теоремы о рекурсии.

[math]\triangleleft[/math]

Теорема:

В заданной полусистеме Туэ задача вывода из слова [math]\alpha [/math] слово [math] \beta[/math] (word problem for semi-Thue systems) неразрешима.

Источники

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера