Кодирование и нумерация машин Тьюринга.

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

Далее команде I машины Т вида qa ® q¢a¢d ставится в соответствие

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

представляющее собой приписывание кодов символов друг к другу. Пусть машина Т имеет алфавиты А = {a₀,a₁,…,a_m} и Q = {q₀,q₁,…,q_n}. Упорядочим пары q_ia_j лексикографически q₁a₀, q₁a₁,…, q₁a_m, q₂a₀,…, q_na₀,…, q_na_m. В соответствии с этим упорядочим команды машины Т

I₁, I₂, … , I_n(m+1) .

Машине Т поставим в соответствие код

Код(Т) = Код(I₁) Код(I₂) … Код(I_n(m+1)),

получаемый приписыванием друг к другу кодов команд. Для машины Т рассмотренного примера (1.3) кодом будет

Код (Т) = 10⁷10³10⁵10⁶10³10⁷10⁶10⁷10⁶10.

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

Т₀, T₁, T₂, … , T_n, …

Поскольку кодирование эффективно, то существует машина Тьюринга, которая по натуральному числу n выдает Код(Т_n) (если такая существует) и обратно, по Код(T_n) выдает ее номер n_T. Пусть f_n(x) - функция, вычисляемая машиной Т_n. Тогда получаем нумерацию всех вычислимых по Тьюрингу функций одного переменного

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

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