Теория алгоритмов и формальных языков. Мелихов А.Н - 38 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

Тогда команде Q будет однозначно соответствовать положительное число
1931315
7532)( ⋅⋅⋅=Qnq , которое и есть гёделевский номер команды Q.
Если задана упорядоченная последовательность команд Q
1
, Q
2
, …, Q
j
,
…, Q
n
, которая задает некоторую МТ Z, то эта последовательность может
быть закодирована следующим числом:
)(
)(
)()(
......32)(
21
n
j
Qnq
n
Qnq
j
QnqQnq
ppZnq ×××××= ,
которое представляет собой геделевский номер МТ Z.
Пример 2.4. Обратимся к синтезированной в разделе 2.2 МТ Z,
выполняющей сложение двух чисел. Учитывая, что
0
xB
=
, а
1
| x= , получаем:
1001
lqxqQ = ;
153911
1
7532)( ⋅⋅⋅=Qnq ;
10112
qxxqQ = ;
1591315
2
7532)( ⋅⋅⋅=Qnq ;
2003
lqxqQ = ;
193915
3
7532)( ⋅⋅⋅=Qnq ;
2124
lqxqQ =
;
1931319
4
7532)( ⋅⋅⋅=Qnq ;
3025
lqxqQ = ;
233919
5
7532)( ⋅⋅⋅=Qnq
;
30136
qxxqQ = ;
2391323
6
7532)( ⋅⋅⋅=Qnq .
Поскольку геделевские номера оказались упорядоченными в соответствии с
нумерацией команд, геделевский номер МТ Z равен:
239132323391919313191939151591315153611
753275327532753275327532
13117532)(
⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅
×××××=Znq
.
Таким образом, каждая МТ получает свой геделевский номер. Поскольку
процедура приписывания номеров является механической, можно поручить
ее в полнение некоторой МТ G
1
. Замети м, что G
1
вычисляет, в частности, и
свой собственный геделевский номер nq(Q
1
). Обратно, существует такая МТ
G
2
, которая для любого положительного числа выдает один из двух
следующих ответов:
- n не является геделевским номером никакой МТ;
- n является геделевским номером МТ Z, имеющей следующие команды….
Отметим, что если G
2
получает на вход число )(
2
Gnqn
=
, то она выдает ответ
второго типа и печатает набор своих команд (точнее говоря, коды команд).

Страницы