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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 55 из 64
© 2003 Галуев Геннадий Анатольевич
котором подмножестве
n
N
), где
n
N
- множество всевозможных упорядоченных n-ок из
N.
Будем исходить теперь из функций, определенных на
n
N
или его подмножест-
ве. Функция f определенная на некотором подмножестве множества
n
N
, является
частично вычислимой, если существует МТz, такая, что для всякой n-ки
),...,,(
21 n
xxx ,
которой соответствует некоторое значение f, выполняется равенство
),...,,(),...,,(
2121 nzn
xxxxxxf
ψ
=
.
Функция f называется вычислимой, если она определена на всем множестве
n
N
и является частично вычислимой.
Примером вычислимой функции является функция f(x,y)=x+y, поскольку ранее
мы для нее построили МТ, вычисляющую значение f(x,y) для любых x и y.
Геделевский номер машины Тьюринга.
Пусть
k
PPP ,...,,
21
соответственно первое, второе и так далее к-ое простое число.
Из теории чисел известно, что любое натуральное число n (положительные целые
числа n=1,2,…) можно представить в виде
k
a
k
aa
PPPn *...**
21
21
=
( то есть в виде произведения простых чисел),
где
k
aa ,...,
1
- целые неотрицательные числа, включая ноль.
Например,
100000
13*11*7*5*3*213 =
112
5*3*260 =
.
Очевидно, что для любого n однозначно определяется набор
k
aa ,...,
1
и, наобо-
рот по любому набору
k
aa ,...,
1
однозначно восстанавливается соответствующее ему
число n. Если для произвольного слова в некотором алфавите ввести определенным
образом числовое кодирование входящих в него букв, то для данного слова можно
найти однозначно определяющее его число n , которое по сути дела будет являться
его числовым именем. В, частности, каждой команде или набору команд, задающих
МТ, можно
сопоставить некоторое целое положительное число. Это число называется
гёделевским номером МТ по имени математика Курта Гёделя, который впервые при-
менил числовое кодирование для обозначения нечисловых объектов в доказательстве
знаменитой теоремы о неполноте арифметики.
Гёдель предложил использовать следующий способ кодирования цепочек. По-
ясним его идею на примере кодирования команд МТ. Пусть задана
команда
211
lqxqQ
=
.
Для того, чтобы закодировать эту команду, необходимо ввести кодирование симво-
лов и мест их расположения в команде. Будем кодировать символы нечетными целы-
ми числами большими единицы
...27_25_23_21_19_17_15_13_11_9_7_5_3
...____________
4433221100
qxqxqxqxqxsrl
а номера их мест в команде – простыми числами
1234…k…
2357…
k
P …
Тогда команде
211
lqxqQ =
будет однозначно соответствовать число
1931315
7532)( ⋅⋅⋅=⋅ Qgn ,
которое и есть гёделевский номер команды Q.
Если задана упорядоченная последовательность команд
n
QQQQ ,...,,,
321
, которая
задает некоторую МТz, то эта последовательность может быть закодирована следую-
щим числом
)(
)(
)()(
......32)(
21
n
j
Qqn
n
Qqn
j
QqnQqn
PPzgn
⋅
⋅
⋅⋅
⋅⋅⋅⋅⋅=⋅ , которое представляет собой гёделевский но-
мер МТz.
Пример.
1001
lqxqQ =
153911
1
7532)( ⋅⋅⋅=⋅ Qgn

Страницы