§ 1.5.4. Геделева нумерация и кодовые числа алгоритмов Маркова

Т.1.5.(3) Теорема

Множество алгоритмов Маркова эффективно перечислимо.

Доказательство

Идея: описать произвольный алгоритм некоторым числом, которое эффективно распознаётся среди натуральных чисел. Тогда применив алгоритм распознавания к натуральному ряду, удастся перенумеровать все нормальные алгоритмы. А это означает, что они эффективно перечислимы.

Произведём кодировку:

Нормальный алгоритм представляет собой набор строк, например:

ab → c

Λ  d •

Пронумеруем символы алфавита. Первые три символа служебные, для них зарезервируем числа 1,2,3.

→ ”1”

Λ ”2”

• ”3”

Остальные символы получают следующие вакантные номера:

a (x₁) ”4”

b (x₂) ”5”

c (x₃) ”6”

. . . .

. . . .

(x_k) “k+3”

Отступление (из области свойств простых чисел). Если мы возьмем ряд простых чисел и каждое из них возведём в какую-нибудь степень, а затем их перемножим, то по полученному числу мы сможем сказать, в какой именно степени были соответствующие простые числа. Это делается путем деления получившегося числа поочередно на простые числа, начиная с двойки, до тех пор, пока возможно деление без остатка. Потом производится деление на 3, потом на 5 и т.д. до тех пор, пока не получится единица.

2^x • 3^y • 5^z •…=N

Например, мы можем рассчитать степени, в которые были возведены простые числа, произведение которых образует 540:

540=2^x • 3^y • 5^z

540/2=270; 270/2=135; 135/3=45; 45/3=15; 15/3=5; 5/5=1

Двойка участвовала в делении 2 раза, тройка - 3 раза, пятерка – 1 раз. Проверим: 2² • 3³ • 5¹ =4 • 27 • 5=540

Возьмём первую строчку алгоритма Маркова и представим её следующим образом:

a b → c

2⁴ • 3⁵ • 5¹ • 7⁶ =A

Полученное натуральное число A является кодом данной строчки (такая нумерация называется Гёделевой).

Аналогично поступаем со второй строчкой алгоритма:

Λ → d •

2² • 3¹ • 5⁷ • 7³ =B

B является кодом второй строчки.

Далее формируем кодовое число всего алгоритма. Для этого выпишем ряд простых чисел и возведем каждое число в соответствующую этой строчке степень.

2^A, 3^B,…

Перемножив эти числа, получим кодовый номер алгоритма.

2^A•3^B…= К

Таким образом, алгоритм представлен в виде произведения простых чисел, взятых в степенях, соответствующих коду каждой строки. Полученное число К является кодом данного алгоритма. При этом по данному коду можно восстановить полностью весь алгоритм.

Теперь возьмем ряд натуральных чисел и применим к нему алгоритм распознавания, определяющий является ли данное число кодом какого либо алгоритма Маркова. Такой алгоритм распознавания будет состоять из двух процедур: сначала по данному числу К вычисляются числа А, B, C… (коды строк), а затем из этих чисел извлекаются соответствующие x, y, z,… (коды символов в рамках каждой строки). Полученные значения проверяются на предмет соответствия формату строк алгоритмов Маркова. Если ответ положительный, то соответствующему числу К присваивается очередной свободный номер. Т.о. каждый алгоритм Маркова получит свой собственный номер, следовательно, нормальные алгоритмы эффективно перечислимы, Q.E.D.