ВУЗ:
Составители:
х.) Эта проблема известна под названием проблемы остановки для
произвольных машин Тьюринга.
Теорема 2.2. Проблема остановки для произвольных машин Тьюринга
алгоритмически неразрешима.
Для доказательства теоремы 2.2 покажем вначале, что существуют
множества, которые являются рекурсивно перечислимыми, но не
рекурсивными.
Рассмотрим множество машин Тьюринга, вычисляющих функции от
одного аргумента. Каждой из этих машин
Z будем предлагать в качестве
исходного задания ее собственный геделевский номер
)(Znqz
=
. Если машина
Z остановится и выдаст некоторый результат, то будем называть ее
самоприменимой. Если машина Z никогда не остановится, то такую машину
будем называть несамоприменимой. Таким образом, на множестве всех
машин мы определили некоторую функцию от z, которая, очевидно, есть
частично вычислимая функция. Для нее можно построить конкретную МТ,
вычисляющую
эту функцию. Для этого необходимо построить сначала
универсальную МТ, вычисляющую значения указанной функции для любых
чисел. В результате множество G геделевских номеров самоприменимых
машин оказывается рекурсивно перечислимым множеством.
Предположим теперь, что множество G является рекурсивным. Это
равносильно рекурсивной перечислимости его дополнения
G . В таком
случае должна существовать МТ, перечисляющая
G
в перечислении
рекурсивно перечислимых множеств Г
0
, Г
1
, …, Г
i
, …. Предположим, что
множество
G имеет в этом перечислении номер
λ
. Поэтому запишем
λ
ГG = .
Тогда для любого натурального числа
Gх ∈ имеет место
λ
Гх ∈ и наоборот,
т.е.
λ
ГxGх ∈↔∈ , где ↔ - знак логической эквивалентности или
равнозначности. Однако из определения самоприменимости следует
х
ГxGх ∉↔∈
, где Г
х
- множество самоприменимых машин, имеющих в
Страницы
- « первая
- ‹ предыдущая
- …
- 40
- 41
- 42
- 43
- 44
- …
- следующая ›
- последняя »
