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

Поставим в соответствие каждой команде программы МТ пятерку чисел < i, j, i ¢, j ¢, k >, где k = 0, если в команде стоит М, k = 1, если Л, k = 2, если П. Тогда каждая команда МТ получает канторовский номер С ⁵ (i, j, i ¢, j ¢, k) = n; k ₁ – n ₁, k ₂ – n ₂, …, k _s – n_s; s = n (m – 1). Машина Тьюринга получает номер N = C _¥ (n ₁, n ₂, …, n_s).