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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 56 из 64
© 2003 Галуев Геннадий Анатольевич
10112
qxxqQ =
1591315
2
7532)( ⋅⋅⋅=⋅ Qgn
2013
lqxqQ =
193915
3
7532)( ⋅⋅⋅=⋅ Qgn
Так как гёделевские номера команд
)3,2,1(
=
jQ
j
оказались упорядоченными в
соответствии с нумерацией команд, то гёделевский номер МТz равен
1939151591315153911
753275327532
532)(
⋅⋅⋅⋅⋅⋅⋅⋅⋅
⋅⋅=⋅ zgn
.
Таким образом, каждая МТ получает свой гёделевский номер. Поскольку процеду-
ра приписывания номеров является механической, можно поручить ее некоторой
MTG
1
. Заметим, что MTG
1
вычисляет, в частности, и вой собственный геделевский но-
мер ng(G
1
). Справедливо также и обратное то есть что существует такая МТG
2
, кото-
рая для любого положительного числа n выдает один из двух ответов:
- n не является геделевским номером никакой МТ
- n является геделевским номером MT
Z
, имеющей следующие команды…
Отметим, что если G
2
, получает на вход число n=ng(G
2
), то оно выдает ответ второго
типа и печатает коды своих команд.
Рекурсивные и рекурсивно перечислимые множества
Рассмотрим некоторую функцию f(x
1
,x
2
,...,x
n
) = Ψ
z
(x
1
,x
2
,...,x
n
). По определению
она частично вычислима, если существует МТz, которая эту функцию вычисляет. Так
как машине Z однозначно сопоставлен геделевский номер z = ng(z), то всякой час-
тично вычислимой функции f(x
1
,x
2
,...,x
n
) можно сопоставить геделевский номер имен-
но той МТ. Которая эту функцию вычисляет. Введем функцию Фz(x
1
,x
2
,...,x
n
) (где z –
целое неотрицательное число, а (x
1
,x
2
,...,x
n
) – некоторая n-ка из N
n
) следующим об-
разом. Если z = ng(z), причем z это МТz, вычисляющая значения f на n-ке
(x
1
,x
2
,...,x
n
), то значение функции Фz(x
1
,x
2
,...,x
n
) совпадают со значением функции
f(x
1
,x
2
,...,x
n
). Если z не является геделевским номером никакой МТ, то значение
функции Фz(x
1
,x
2
,...,x
n
) = 0. В результате мы получим вычислимую функцию и можем
теперь записать последовательность Ф
0
, Ф
1
, …,Ф
n
, … Которая перечисляет (быть мо-
жет с повторением) множество частично вычислимых функций от n аргументов. Таким
образом мы можем в принципе перечислять области определения частично вычисли-
мых функций.
Пусть заданы теперь произвольные Z и (x
1
,x
2
,...,x
n
). Тогда. Чтобы вычислить
значения функции Фz(x
1
,x
2
,...,x
n
), необходимо сначала вычислить являются ли Z ге-
делевскими номерами какой-либо МТ. Эту задачу решает МТ
G2
, введенная выше. Ес-
ли Z не является геделевским номером. То Фz(x
1
,x
2
,...,x
n
) = 0. в противном случае
МТz, команды которые распечатываются MTG
Z
, предлагается (x
1
,x
2
,...,x
n
) в качестве
исходного задания. Соединяя G
Z
и Z, мы получаем универсальную МТ, вычислитель-
ную функцию Фz(x
1
,x
2
,...,x
n
). Если на ленте этой машины поместить число z = ng(z),
то она сможет вычислить функцию соответствующую этому числу.
Пусть X произвольный элемент множества М и А<М. Характеристическая функ-
ция подмножества А. обозначаемая C
A
определяется следующим образом
Будем говорить, что множество называется рекурсивным
, если его
⎩
⎨
⎧
∉
∈
=
Ахесли
Ахесли
xC
A
,0
,1
)(

Страницы