Составители:
Рубрика:
называют характеристической функцией множества A.
Множество A называют рекурсивным (разрешимым), если его
характеристическая функция рекурсивна.
Множество называют рекурсивно-перечислимым, если оно
является областью определения некоторой ЧР-функции.
Теорема 4.3. Множество рекурсивно тогда и только тогда,
когда оно само и его дополнение рекурсивно-перечислимы.
Доказательство. Пусть множество R рекурсивно. Тогда
существует машина Тьюринга M, которая вычисляет его
характеристическую функцию. Изменим M так, чтобы получить две
машины, вычисляющие функции
1, если x ∈ R;
не определена, если x ∉ R.
f (x) =
0, если x ∈⎯R;
не определена, если x ∉⎯R.
Следовательно, из рекурсивности R следует, что R и ⎯R рекурсивно-
перечислимые множества.
Предположим теперь, что R и ⎯R рекурсивно-перечислимые
множества. В таком случае они являются областями определения
частично-вычислимых функций f(x) и
⎯
f(x), для которых имеются
вычисляющие их машины Тьюринга Z и
⎯
Z соответственно. Если
предложить этим машинам некоторое задание x, то одна из них
обязательно даст результат, а другая нет. Если это машина Z, то
χ
R
(x)=1, а если это машина ⎯Z, то χ
R
(x)=0. Пара машин ⎯Z и Z
эквивалентна одной машине Тьюринга. Следовательно, χ
R
(x)
вычислима, а R и ⎯R – рекурсивные множества. Доказательство
закончено.
Теорема 4.4. Проблема останова алгоритмически
неразрешима.
Доказательство. Предположим, что существует машина
Тьюринга T, которая, получив задание z*X, даст ответ
⎯
f
(
x
)
=
165
Страницы
- « первая
- ‹ предыдущая
- …
- 79
- 80
- 81
- 82
- 83
- …
- следующая ›
- последняя »
