ВУЗ:
Составители:
Пусть х - произвольный элемент множества М и
M
A
⊂ .
Характеристическая функция подмножества А, обозначаемая С
А
,
определяется следующим
⎪
⎩
⎪
⎨
⎧
∉
∈
=
.,0
,,1
)(
Axиесл
Axесли
xC
A
Будем говорить, что множество называется рекурсивным, если его
характеристическая функция вычислима. Если множество рекурсивно, то
существует МТ, которая, получив на вход элемент этого множества, всегда
ставит ему в соответствие некоторый ответ: либо 1 (и тогда
Ах ∈ ), либо 0
(
Ах ∉ ).
Будем говорить, что множество называется рекурсивно перечислимым,
если оно является областью определения некоторой частично вычислимой
функции. Теоретически можно перечислить частично вычислимые функции
от одной целочисленной переменной, от двух целочисленных переменных и
так далее. Следовательно, в принципе мы умеем перечислять рекурсивно
перечислимые множества: Г
0
, Г
1
, …, Г
i
, ….
Теорема 2.1. Множество является рекурсивным тогда и только тогда,
когда оно само и есть дополнение рекурсивно перечислимы.
Доказательство. Пусть М - произвольное множество,
M
A
⊂ и А
является рекурсивным множеством. Тогда характеристическая функция С
А
множества А является вычислимой определению рекурсивности множества
А. Представим
)(хС
А
в виде объединения двух функций:
⎪
⎩
⎪
⎨
⎧
∈
∈
=
′
,,
,,1
)(
Ахеслиопределенане
Ахесли
хС
А
⎪
⎩
⎪
⎨
⎧
∈
∈∈
=
′
.,
),\..(,0
)(
Ахеслиопределенане
АМхетАхесли
хС
А
Каждая из указанных функций является частично вычислимой функцией по
определению частично вычислимой функции. Отсюда на основании
определения рекурсивно перечислимых множеств множества А и
А являются
рекурсивно перечислимыми множествами.
Предположим теперь, что множества А и
А рекурсивно перечислимы.
Тогда они являются областями определения частично вычислимых функций
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
