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