15. Нумерация алгоритмов. Нумерация машин Тьюринга

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

Нумерация машин Тьюринга

Зафиксируем счетные множества символов {A0, A1, …, AI, …} и {Q0, Q1, …, QJ, …} и будем считать, что внешние алфавиты и алфавиты внутренних состояний всех машин Тьюринга берутся из этих множеств. При этом будем считать, что A0 принадлежит всем внешним алфавитам машин и интерпретируется как пустой символ, а буквы Q0, Q1 принадлежат всем внутренним алфавитам машин и всегда означают заключительное и начальное состояния соответственно. Опишем теперь единый способ представления информации о машинах с помощью кодирования. Каждому символу из множества {L, R, E, A0, A1, …, AI, …, Q0, Q1, …, QJ, …} поставим в соответствие двоичный набор согласно табл.15.1.

Далее, команде I машины Тьюринга Т, имеющей вид Qa à Q’A’D, ставится в соответствие двоичный набор вида

Код (I) = Код(Q) Код(A) Код(Q’) Код(A’) Код(D),

В котором коды букв приписаны друг к другу. Пусть машина Т имеет алфавиты A = {A0, A1, …, AM} и Q = {Q0, Q1, …, QN}. Упорядочим команды машины Т в соответствии с лексикографическим порядком левых частей команд:

Q1, A0, Q1, A1, …, Q1, AM, Q2, A0, …, Q2, AM, …, QN, A0, …, QN, AM.

Пусть I1, …, IN(M+1), — соответствующая последовательность команд. Тогда машине Т поставим в соответствие двоичный набор вида

Код(T) = Код(I1) Код(I2)… Код(IN(M+1)),

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

Таблица 15.1

	Символ	Код	Число нулей в коде
Символы сдвига	R L E	10 100 1000	1 2 3
Символы алфавита ленты	A0 A1 … AI …	10000 1000000 … 100…00 …	4 6 … 2×I + 4 …
Символы алфавита состояний	Q0 Q1 … QI …	100000 10000000 … 100…00 …	5 7 … 2×J + 5 …

Пример 15.1. Пусть дана машина Тьюринга Т. A = {A0, A1} и Q = {Q0, Q1}:

.

Тогда имеем Код(T) = 107104105104103107106105106103.

Легко видеть, что машина Т переводит конфигурации в конфигурации , и поэтому, представляя натуральное число N как , получаем, что машина Т вычисляет функцию F(X) = X.

Ясно, что указанное кодирование является алгоритмической процедурой. Имея код машины, однозначно восстанавливается множество ее команд — для этого надо выделить подслова, начинающиеся с единицы с нулями до следующей единицы. Пятерка таких подслов образует команду. Далее, легко видеть, что имеется алгоритмическая процедура, позволяющая по произвольному слову из 0, 1 выяснять — будет ли это слово служить кодом некоторой машины Тьюринга. Будем теперь рассматривать код машины Тьюринга как двоичную запись натурального числа. Данное число назовем номером машины Тьюринга. Поскольку все коды начинаются с единицы, то разным кодам соответствуют разные числа. Упорядочим машины Тьюринга по возрастанию чисел, представляемых их кодами, и занумеруем их Т0, Т1, …, ТN, … .

Номер машины Т в этом упорядочении будем обозначать NT.

Указанное упорядочение является эффективным в том смысле, что существует алгоритм, который по N выдает Код(TN) и существует алгоритм, который, наоборот, по Код(TN) выдает NT.

Если обозначить через FN(X) одноместную функцию, которую вычисляет машина Тьюринга TN, то в результате получим нумерацию всех одноместных частично рекурсивных функций:

F0(X), F1(X), …, FN(X), …

Согласно доказанному, каждая одноместная частично рекурсивная функция представлена в этой последовательности. Можно доказать, что каждая такая функция представлена в последовательности (5) бесконечное число раз. Аналогично можно определить нумерацию N-местных функций.

< Предыдущая		Следующая >