1) Пусть последовательность k0k2kzимеет видq0a2a1a4q1a1qza4a2(очевидно, что последовательность команд следующая:q0a2q1a4 dп,q1a1qza2dЛ).

Имеем следующую интерпретацию смены ситуаций:

2) Машина Т=<a₀, a, q₀, q_z, q₀ a₀ q₀ a d_п, q₀ a q₀ a d_п> будет работать бесконечно, заполняя все ячейки ленты символами а вправо от начальной пустой ячейки (исходная информация на ленте - пустые символы а₀ в каждой ячейке ленты).

Примечания:

1. Соответствие, устанавливаемое машиной Тьюринга между теми исходными данными, к которым она применима ( то есть если она приводит к результату) и результатами ее работы представляет собой некоторую словарную функцию (в математическом смысле) Т(^*_исх^*_рез_исх_рез_пром.

2. Если для функции имеется машина ее реализующая, то говорят, что эта функция вычислима по Тьюрингу. Функция, для вычисления которой существует алгоритм, называется вычислимой.

3. Поскольку слово (^*, m) можно отождествить с натуральным числом (в m-ичной системе счисления), то уточнение понятия вычислимой словарной функции приводит и к уточнению понятия вычислимой числовой функции f:N^kN, kN. Тьюринг доказал. что класс числовых функций, вычислимых на машине Тьюринга, совпадает с классом частично-рекурсивных функций.