ВУЗ:
Составители:
2.5. Геделевский номер машины Тьюринга
Пусть р
1
, р
2
, …, р
k
- соответственно первое, второе и так далее k-е
простое число. Из теории чисел известно, что любое целое неотрицательное
число
1≥n можно однозначно представить в форме:
k
a
k
aa
pppn ×××= ...
21
21
,
где а
1
, а
2
, …, а
k
- некоторые целые неотрицательные числа, включая ноль.
Например,
100000
1311753213 ⋅⋅⋅⋅⋅= ,
112
53260 ⋅⋅= . Очевидно, что для любого n
однозначно определяется набор а
1
, а
2
, …, а
k
и, наоборот, по любому набору
а
1
, а
2
, …, а
k
однозначно восстанавливается соответствующее ему число n.
Если для произвольного слова в некотором алфавите ввести
определенным образом числовое кодирование входящих в него букв, то для
данного слова можно найти однозначно определяющее его число n, которое
по сути дела будет являться его числовым именем. В частности, каждой
команде или набору команд, задающих
МТ. можно сопоставить некоторое
целое положительное число. Это число называется гёделевским номером МТ
по имени математика Курта Геделя, который впервые применил числовое
кодирование для обозначения нечисловых объектов в доказательстве своей
знаменитой теоремы о неполноте арифметики.
Гедель предложил использовать следующий способ кодирования
цепочек. Поясним его идею на примере кодирования команд МТ
. Пусть
задана команда
211
lqxqR = . Для того, чтобы закодировать эту команду,
необходимо ввести кодирование символов и мест, которые они занимают в
команде. Будем кодировать символы нечетными числами большими
единицы:
,
...2725232119171513119753
...
4433221100
qxqxqxqxqxsrl
а номера мест - простыми числами:
......7532
......4321
k
p
k
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
