ВУЗ:
Составители:
f(x) и )(xf , совпадающих соответственно с )(xC
A
′
и )(xC
A
′
. Для этих функций
можно построить вычисляющие их МТ соответственно Z и
Z
. Пусть на
входы машин Z и
Z
поступает элемент Mx
∈
. Тогда одна из машин
обязательно выдаст некоторый результат, а другая нет. Действительно, если
результат дает машина Z, то
1)(
=
′
xC
A
и
Ах ∈
. Если же результат дает машина
Z
, то 0)( =
′
xC
A
и Ах ∈ . Пара машин Z,
Z
эквивалентна некоторой одной МТ
Z′, вычисляющей значения функции
)(xC
A
. Поэтому множество является
рекурсивным. Более того, множество
А также рекурсивно, поскольку Z′
вычисляет и значения характеристической функции множества
А :
⎪
⎩
⎪
⎨
⎧
∈∨∉∉
∈
=
)...(,,1
,,0
)(
АхМхетАхесли
Ахесли
хС
А
Этим теорема 2.1 доказана.
Теорема 2.1 утверждает, что любое рекурсивное множество является
рекурсивно перечислимым, но оставляет открытым вопрос о том, любое ли
рекурсивно перечислимое множество является рекурсивным? Ниже будет
показано, что существуют множества, которые являются рекурсивно
перечислимыми, но не рекурсивными.
2.7. Неразрешимость проблемы остановки для произвольных
машин Тьюринга
Сформулируем следующую проблему
: существует ли машина
Тьюринга Z, для которой входными заданиями являются пары (z, x), где
)(Znqz = , а х - произвольное натуральное число, такая, что при поступлении
на вход МТ Z исходных данных х, она отвечала бы: либо «да, ТМ Z
применима к х, т.е. начав вычисления с х, выдает некоторый результат и
остановится», либо «нет, предлагать МТ Z заданные х не следует, так как она
никогда
не остановится». (В этом случае говорят, что МТ Z не применима к
Страницы
- « первая
- ‹ предыдущая
- …
- 39
- 40
- 41
- 42
- 43
- …
- следующая ›
- последняя »
