Нумерация МПД-программ

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

a(Z (n)) = 4×(n – 1),

a(S (n)) = 4×(n – 1) + 1,

a(T (m, n)) = 4× p (m – 1, n – 1) + 2,

a(J (m, n, q)) = 4×p(m, n, q) + 3,

где p (x, y) = 2 ^x ×(2 y + 1) – 1, p(x, y, z) = p (p (x – 1, y – 1), z – 1).

Ясно, что функция aэффективно вычислима. Для вычисления действуем так:

Находим числа u, v, такие, что x = 4 u + v, где . Тогда имеем:

= Z (u + 1), если v = 0;

= S (u + 1), если v = 1;

= T (l (u) + 1, r (u) + 1), если v = 2;

= J (m, n, q), если v = 3, где (m, n, q) = .

Следовательно, функция также эффективно вычислима.

Пусть теперь дана МПД-программа P = I ₁... I_s. Определим ее номер g(Р) = t(a(I ₁), …, a(I_s)), где

t(x ₁, …, x_s) = .

Ясно, что тем самым определена биекция g множества программ в множество натуральных чисел, причем функции g и g^-1 эффективно вычислимы, по программе Р эффективно находится ее номер n = g(P), а по номеру n можно эффективно найти программу Р такую, что n = g(P). Число g(P) называется номером программы Р. Например, если Р = I ₁ I ₂ I ₃, где I ₁ = T (3, 1), I ₂ = S (4), I ₃ = Z (6), то

a(T (3, 1)) = 18, a(S (4)) = 13, a(Z (6)) = 20.

Следовательно, g(P) = 2¹⁸2³²2⁵³ – 1. Пусть теперь дано n = 4127. Поскольку 4127 = 2⁵ + 2¹² – 1, то Р = I ₁ I ₂, где a(I ₁) = 5, a(I ₂) = = 18 – 5 – 1. Следовательно, I ₁ = S (2), I ₂ = T (2, 1).

Разумеется, существуют и другие способы нумерации программ, для нас важна лишь эффективная вычислимость функций g и g^-1.

Таким образом, получаем эффективную нумерацию МПД-программ:

P ₀, P ₁, P ₂, …, P_n, ….

Теперь, имея нумерацию МПД-программ, можно занумеровать МПД-вычислимые функции. Для любого a Î N и n ³ 1 определим n -местная функция, вычислимая программой с номером а. Это дает нумерацию n -местных МПД-вычислимых функций , , , …

Например, если а = 4127, то согласно определению имеем:

, n = 1;

, n > 1.

Поскольку для всякой частично рекурсивной функции существует вычисляющая ее МПД-программа Р, то , где a = g(P). Число а называют номером (индексом) функции .

Приведем одно применение существования нумерации частично рекурсивных функций.

Теорема 15.2. Существует всюду определенная функция, не являющаяся частично рекурсивной.

Доказательство. Построим всюду определенную функцию j, отличающуюся от каждой частично рекурсивной функции f ₀, f ₁, …, f_n, … в перечислении одноместных частично рекурсивных функций. Полагаем

Функция j всюду определена и отличается от f_n при x = n, n Î N ₀. Действительно, если f_n (n) определено, то j(n) = f_n (n) + 1, если f_n (n) не определено, то j(n) определено и равно 0. Поскольку j отличается от f_n при всех n Î N ₀, то j не может находиться в перечислении (10) и, значит, она не может быть частично рекурсивной, что и требовалось доказать.

Замечание. 15.3. Приведенный метод рассуждения есть пример диагональной конструкции Кантора, с помощью которой им была доказана несчетность множества действительных чисел. Данным методом можно установить нерекурсивность большого класса функций.

Например, функция

причем p (x) — целочисленный полином является всюду определенной и не частично рекурсивной.

Дата добавления: 2014-12-29