геделева нумерация программ (17)


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Число (
P
) называется

геделевым номером

программы

P

или просто

номером
программы

P.

Отображение играет важную роль в теории алгоритмов. Название числа (
P
)
связано с именем К.

Геделя, впервые в 1931 году предложившего идею
кодирования нечисловых объектов нат
уральными числами.

Ниже программу

P

с геделевым номером

n

будем обозначать

. Из взаимной
однозначности отображения следует


при

, хотя обе эти
программы


и


могут вычислять одну и ту же функцию.

Пример 4.1. Найдем геделев номер программы

P
:

,

,

вычисляющей функцию

f
(
x
)

=

x

+

2.

.

(
S
(
1
)) =

4

(1

-

1
)

+

1

=

1
;

.

Пример 4.2. Вычислим программу


по ее геделеву номеру

m
.

1)

m

=

0.

;

.

Следовательно,

:

1
.

Z
(
1
).

2)

m

=

1.

;

.

Следовательно,

:

1.

S
(
1
).

3)

m

=

2.

;

.

Следовательно,

:

1.

Z
(
1
),

2.

Z
(
1
).

4)

m

=

3.

;

.

Следовательно,

:

1.

T
(
1,

1
).

Заметим, что различные программы


и


вычисляют одну и ту же
функцию

f
(
x
)

=

0
.




Приложенные файлы

  • pdf 13051320
    Размер файла: 188 kB Загрузок: 3

Добавить комментарий