Составители:
Рубрика:
• “да”, если машина Z с геделевским номером z, получив
задание X, отработает, остановится и выдаст некоторый
результат;
• “нет”, если машина Z с входным заданием X никогда не
остановится.
Пусть E - рекурсивно-перечислимое, но не рекурсивное множество.
Тогда E является областью определения некоторой ЧР-функции f
m
,
вычисляемой машиной M. Машина T для любого натурального x дала
бы ответ
• “да, x ∈ E и M остановится ”;
• “нет, x ∉ E и M не остановится ”.
Это означало бы, что E – рекурсивное множество, что противоречит
предположению о свойствах этого множества. Следовательно,
машина Тьюринга T не может существовать.
Остается показать, что существуют рекурсивно-перечислимые,
но не рекурсивные множества. Для этого рассмотрим множество
машин Тьюринга, вычисляющих функции одного аргумента. Каждой
такой машине предложим в качестве исходного задания ее
собственный геделевский номер z. Если машина Z, начав вычисления
с z=Ш(Z), когда-либо остановится, то она называется
самоприменимой.
Таким образом, мы можем построить функцию Q
z
(Z).
Очевидно, что Q
z
(Z) – частично вычислимая функция.
Следовательно, множество G геделевских номеров
самоприменимых машин рекурсивно-перечислимо.
Предположим, что это множество является также и
рекурсивным. Это значит, что
⎯
G также рекурсивно-перечислимо.
Тогда должна существовать машина Тьюринга с номером λ,
перечисляющая
⎯
G (т.е. вычисляющая некоторую функцию с
областью определения
⎯
G).
В перечислении рекурсивно-перечислимых множеств
множество
⎯
G имеет именно этот конкретный номер:
⎯
G =R
λ
. Тогда
для любого натурального x мы имели бы x ∈ R
λ
⇔ x ∈ R
x
. Ecли
166
Страницы
- « первая
- ‹ предыдущая
- …
- 80
- 81
- 82
- 83
- 84
- …
- следующая ›
- последняя »
