Математическая логика и теория алгоритмов. Галуев Г.А. - 57 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 57 из 64
© 2003 Галуев Геннадий Анатольевич
характеристическая функция вычислима. Если множество рекурсивно, то существует
МТ, которая, получив на вход элемент этого множества, всегда ставит ему в соответ-
ствие некоторый ответ: либо 1, либо 0. (т.е.
AxлибоAx
∉
∈
).
Будем говорить, что множество называется рекурсивно-перечислимым, если
оно является областью определения некоторой частично вычислимой функции. Тео-
ретически можно перечислить частично-вычислимые функции от 1,2 и т.д. целочис-
ленных переменных. Следовательно в принципе мы умеем перечислять и рекурсивно
перечислимые множества Г
0
, Г
1
, …, Г
i
,…
С учетом сказанного имеет место следующая
т
т
е
е
о
о
р
р
е
е
м
м
а
а
:
: Множество является ре-
курсивным тогда и только тогда, когда оно само и его дополнение рекурсивно пере-
числимы.
Эта теорема по сути дела утверждает, что любое рекурсивное множество рекур-
сивно перечислимым. Однако она оставляет открытым вопрос о
том, любое-ли множе-
ство является рекурсивным. Далее мы покажем, что существуют множества некото-
рые являются рекурсивно перечислимыми, но не являются рекурсивными.
Неразрешимость проблемы остановки для
произвольных машин Тьюринга.
Сформулируем следующую проблему: существует ли МТ, для которой входны-
ми заданиями являются пары (Z,X) (где z = ng(z), а x-произвольное натуральное
число), такая, что при поступлении на вход МТz исходных данных Х она отвечала-бы:
либо «да, МТz применима к Х, т.е. начав вычисление с Х, выдает некоторый результат
и остановится», либо «нет, предлагать
МТz задание Х не следует, т.к. она никогда не
остановится». (в этом случае говорят что МТ не применима к Х). Эта проблема из-
вестна под названием проблемы остановки для произвольных машин Тьюринга. Су-
ществует теорема.
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
.
. Проблема остановки для произвольных машин Тьюринга
алгоритмически
неразрешима.
Для доказательства этой теоремы покажем сначала, что существуют множества,
которые являются рекурсивными.
Рассмотрим множество машин Тьюринга, вычисляющих функции от одного ар-
гумента. Каждой их этих машин Z будем предлагать качестве исходного задания ее
собственный геделевский номер z = ng(z). Если машина Z остановится и выдаст неко-
торый результат, то будем называть ее несамоприменимой.
Таким образом, на мно-
жестве всех машин мы определим некоторую функцию от Z, которая очевидно, час-
тично вычислимая функция. Для нее можно построить конкретную МТ, вычисляющую
этой функцию. Для этого необходимо построить сначала универсальную МТ, вычис-
ляющую значения этой функции для любых чисел. В результате множество G геде-
левских номеров самоприменимых машин будет
рекурсивно-перечислимым множест-
вом.
Предположим теперь, что множество G является рекурсивным. Это равносильно
рекурсивной перечислимости его дополнения Ğ. В таком случае должна существовать
МТ, перечисляющая Ğ в перечислении рекурсивно перечислимых множеств
Г
0
, Г
1
, …, Г
i
,…
Предположим, что множество Ğ имеет в этом перечислении номер λ. Поэтому
запишем Ğ=Г
λ
. Тогда для любого натурального Х
∈
Ğ ↔ Х
∈
Г
λ
(↔ знак логической эк-
вивалентности). Однако из определения самоприменимости следует Х
∈
Ğ ↔ Х
∈
Г
х
,
где Г
х
– множество самоприменимых машин, имеющих в перечислении Г
0
, Г
1
, …, Г
i
,…
номер х. Отсюда вытекает Х
∈ Г
λ
↔ Х
∉
Г
х.
Если теперь положить Х = λ, то имеем Х
∈
Ğ
↔ Х
∉Г
λ
. Полученное противоречие доказывает, что множество G не является рекур-
сивным. Итак, действительно, не всякое множество, являющееся рекурсивно пере-
числимым является и рекурсивным.
Предположим теперь, что существует машина Т. Которая для произвольной па-
ры (z,x) решает проблему остановки. Пусть G – рекурсивно перечислимое, но не ре-

Страницы