ВУЗ:
Составители:
Пока МТ Z выполняет вычисления над числами n в соответствии с
командами, начиная с аксиомы
hnhq
o
формируется вывод в полутуэвской
системе по принципу: одна переменная команда МТ Z - один шаг вывода в
системе. Как только МТ Z остановилась, к полученной формуле системы
применяются дополнительные подстановки, которые в конечном итоге
приводят к формулам hsh. Тем самым теорема доказана.
Заметим, что в системе П от числа n зависит
только аксиома hnhq
o
, а
алфавит и подстановки от n не зависят. Если n принимает значения из
множества целых неотрицательных чисел, то действуя таким образом, как
указано в доказательстве теоремы 2.3, мы получим семейство полутуэвских
систем типа П. С помощью этого семейства множеству тех чисел n, к
которым применима МТ Z, ставится в соответствие единственная
формула
hsh. Это наводит на мысль о том, что можно построить систему П, которая,
исходя из аксиомы hsh, выдавала бы в качестве заключительных формул все
целые числа, к которым применима МТ Z. Действительно, для построения в
качестве аксиомы можно выбрать hsh, а в качестве системы подстановок -
подстановки, обратные подстановкам системы П
. Если объединить системы
П и П′ (при этом в качестве аксиомы объединенной системы принять hsh), то
легко видеть, что МТ Z будет соответствовать туэвская система Т.
В заключение раздела отметим следующее. Построенные
комбинаторные системы П, П′ и Т, соответствующие МТ Z, сопоставляют
входным словам машины Z формулы в указанных
системах. Выбрав в
качестве Z такую машину, для которой неразрешима проблема остановки, мы
приходим к выводу о том, в соответствующих полутуэвской и туэвской
системах неразрешима проблема доказуемости. Суть этой проблемы состоит
в следующем: можно ли построить алгоритм, который бы однозначно
определял, является или нет некоторое слово формулой данной системы?
Очевидно,
что проблема доказуемости неразрешима и для нормальных и
постовских систем.
Страницы
- « первая
- ‹ предыдущая
- …
- 44
- 45
- 46
- 47
- 48
- …
- следующая ›
- последняя »
