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

Нумерация алгоритмов

Л е к ц и я 15

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

Зафиксируем счетные множества символов { a ₀, a ₁, …, a_i, …} и { q ₀, q ₁, …, q_j, …} и будем считать, что внешние алфавиты и алфавиты внутренних состояний всех машин Тьюринга берутся из этих множеств. При этом будем считать, что a ₀ принадлежит всем внешним алфавитам машин и интерпретируется как пустой символ, а буквы q ₀, q ₁ принадлежат всем внутренним алфавитам машин и всегда означают заключительное и начальное состояния соответственно. Опишем теперь единый способ представления информации о машинах с помощью кодирования. Каждому символу из множества { L, R, E, a ₀, a ₁, …, a_i, …, q ₀, q ₁, …, q_j, …} поставим в соответствие двоичный набор согласно табл.15.1.

Далее, команде I машины Тьюринга Т, имеющей вид qa à q’a’d, ставится в соответствие двоичный набор вида

Код (I) = Код (q) Код (a) Код (q ’) Код (a’) Код (d),

в котором коды букв приписаны друг к другу. Пусть машина Т имеет алфавиты A = { a ₀, a ₁, …, a_m } и Q = { q ₀, q ₁, …, q_n }. Упорядочим команды машины Т в соответствии с лексикографическим порядком левых частей команд:

q ₁, a ₀, q ₁, a ₁, …, q ₁, a_m, q ₂, a ₀, …, q ₂, a_m, …, q_n, a ₀, …, q_n, a_m.

Пусть I ₁, …, I_{n ( m +1)}, — соответствующая последовательность команд. Тогда машине Т поставим в соответствие двоичный набор вида

Код (T) = Код (I ₁) Код (I ₂)… Код (I_{n ( m +1)}),

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

Таблица 15.1

	Символ	Код	Число нулей в коде
Символы сдвига	R L E
Символы алфавита ленты	a 0 a 1 … ai …	… 100…00 …	… 2× i + 4 …
Символы алфавита состояний	q 0 q 1 … qi …	… 100…00 …	… 2× j + 5 …

Пример 15.1. Пусть дана машина Тьюринга Т. A = { a ₀, a ₁} и Q = { q ₀, q ₁}:

.

Тогда имеем Код (T) = 10⁷10⁴10⁵10⁴10³10⁷10⁶10⁵10⁶10³.

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

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

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

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

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

f ₀(x), f ₁(x), …, f_n (x), …

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

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