6.2 Нумерация программ

Теорема 6.2 Все программы на языке МНР можно эффективно перенумеровать, то есть каждой программе соответствует некоторый номер так, что разным программам соответствуют разные номера, и в то же время каждому натуральному числу будет соответствовать некоторая программа.

Доказательство. Сначала научимся нумеровать команды МНР.

Где π – некоторая специальная функция, нумерующая пары натуральных чисел. В качестве примера такой функции приведем π(m,n)=2^m-1(2n-1).

Заметим, что функция π – хорошая. То есть разным парам соответствуют разные числа и каждому числу соответствует некоторая пара. Кроме того, обе функции – прямая (π) и обратная (π^-1) эффективно вычислимы. Покажем это:

π(3,4) = 2²(2∙4-1)=4∙7=28

π^-1(28)=2^2

° - ставим 2, так как это максимальная степень двойки, на которую делится 28

π^-1(54)= π^-1(2∙27)= π^-1(2(2∙14-1))=(2,14)

π^-1(100)=(3,13)

Рассмотрим примеры кодировки команд:

Т(3,2)→4π(3,2)-1=2²(2∙2-1)=4∙48-1=191

J(2,1,3)4π(2,π(1,3))=4π(2,5)=4∙29=72.

Построенная нами нумерация хорошая, так как:

во-первых, разным командам соответствуют разные числа,

во-вторых, каждому натуральному числу соответствует некоторая команда,

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

Пример.

Определить команду имеющую код 247.

1. Определяем остаток от деления на 4: 247 div 4=3

2. Так как получено 3, значит мы, при вычислении номера команды, вычитали1, следовательно, мы переводили в число команду Т.

3. Восстанавливаем обратно: 247+1=248=4∙62

Π(k,l)=62

k=2

l=16

Результат: Т(2,16).

Определить команду. Имеющую код 264.

1. 264 div 4 = 0

2. J(m,n,q)=4π(m,π(n,q))

3. 264=4∙66

66=π(m,π(n,q))

m=2

n=2

q=9

Результат: J(2,2,9).

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

Делаем это следующим способом.

Рассмотрим функцию φ, которая переводит в набор из k натуральных чисел в натуральное число по следующей формуле:

φ(n₁,n₂..n_k) =

Если число φ(n₁,n₂..n_k) записать в двоичной записи, то оно может, у примеру выглядеть так:

Φ(1,2,3)=2⁰+2²+2⁵=100101

Φ^-1(13)=(1,2,1) так как 13 1101

Таким образом, функция φ – хорошая, так как:

1. Разные наборы переходят в разные числа;

2. Каждому натуральному числу соответствует набор чисел, который в него приходит;

3. Функции φ и φ^-1 эффективно вычислимы.

4. Таким образом мы научились нумеровать все программы на языке МНР и доказали Теорему 6.2

Теорема доказана.