|
|
| Строка 9: |
Строка 9: |
| | | | |
| | Вывод <tex>\beta</tex> из <tex>\alpha</tex> - цепочка <tex>\alpha\vDash\epsilon_1\vDash\epsilon_2\vDash .. \vdash\beta</tex>, где каждое <tex>\epsilon_j</tex> получается из <tex>\epsilon_{j-1}</tex> некоторой подстановкой. | | Вывод <tex>\beta</tex> из <tex>\alpha</tex> - цепочка <tex>\alpha\vDash\epsilon_1\vDash\epsilon_2\vDash .. \vdash\beta</tex>, где каждое <tex>\epsilon_j</tex> получается из <tex>\epsilon_{j-1}</tex> некоторой подстановкой. |
| − |
| |
| − | <tex>\delta</tex> заключительное, если оно выводимо в системе и к нему неприменима ни одна из подстановок.
| |
| | | | |
| | {{Определение | | {{Определение |
| | |definition = | | |definition = |
| − | '''Система Туэ (ассоциативное исчисление)''' - это формальная система, определяемая алфавитом <tex>A</tex> | + | '''Проблема останова (halting problem)''' - это задача, в которой требуется по заданной программе проверить завершиться ли она на определенных входных данных. |
| − | и конечным множеством соотношений вида <tex>\alpha_i\leftrightarrow \beta_i</tex>, которые понимаются как пара левой и правой подстановки, где <tex>\alpha_i, \beta_i</tex> - слова, возможно, пустые, в <tex>A</tex>.
| |
| | }} | | }} |
| | | | |
| − | Таким образом, ассоциативное исчисление всегда есть система подстановок.
| |
| − |
| |
| − | Полусистеме и системе Туэ можно поставить в соответствие машину Тьюринга.
| |
| − |
| |
| − | Пусть <tex>A_T</tex> - алфавит машины Тьюринга, тогда <tex>A_S = A_T\cup \{ q_1, ... q_z\}</tex>
| |
| − | Системе команд соответствует система соотношений
| |
| − | <tex>q_ia_i \rightarrow q_ia_lR</tex>; <tex>q_ia_j \rightarrow a_lq_k</tex>;
| |
| − | <tex>q_ia_i \rightarrow q_ka_lL</tex>; <tex>a_iq_ia_j \leftrightarrow q_ka_ta_l</tex> для любого <tex> a_t \in A_T </tex>
| |
| − | {{Теорема
| |
| − | |id=th1
| |
| − | |about=
| |
| − | |statement=
| |
| − | В исчислении <tex>S(T)</tex> слова <tex>\alpha q_i a_j \beta \Leftrightarrow \gamma q_z a_k \delta</tex> тогда и только тогда, когда машина <tex>T</tex> из конфигурации <tex>\alpha q_i a_j \beta </tex> переходит в конфигурацию <tex>\gamma q_za_k\delta</tex> за конечное число тактов.(1)
| |
| − | }}
| |
| | {{Теорема | | {{Теорема |
| | |id=th1 | | |id=th1 |
| − | |about= Маркова-Поста
| |
| | |statement= | | |statement= |
| − | Существует ассоциативное исчисление, в котором проблема распознования эквивалентности слов алгоритмически неразрешима. | + | Проблема останова неразрешима. |
| | |proof= | | |proof= |
| | | | |
| − | Возьмем какую-нибудь универсальную правильновычисляющую машину Тьюринга. Построим <tex>S(U)</tex> и присоединим к нему <tex>q_za_i \leftrightarrow q_z</tex>, чем получим S'(U). В такой системе тоже можно имитировать исчислительный процесс <tex>U</tex>, как и в <tex>S(U)</tex>. Однако благодаря новым соотношениям все заключительные конфигурации <tex>U</tex> в <tex>S'(U)</tex> эквивалентны <tex>q_z</tex>. Поэтому для <tex>S'(U)</tex> (1) принимает вид: в <tex>S'(U)</tex> слова <tex>q_1\alpha</tex> и <tex>q_z</tex> эквивалентны тогда и только тогда, когда <tex>U</tex>, начав с <tex>q_1\alpha</tex>, остановится. Проблема останова для унивирсальной машины Тьюринга неразрешима.
| + | Доказательство теоремы приведено в примере использования [[Теорема_о_рекурсии|теоремы о рекурсии]]. |
| | }} | | }} |
| | | | |
| | == Источники == | | == Источники == |
| | Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера | | Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера |
| Определение: |
| Полусистема Туэ (система подстановок) - это формальная система, определяемая алфавитом [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] |
Источники
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера
