Машина Тьюринга

тренажер для изучения универсального исполнителя

Что это такое?

Тренажёр «Машина Тьюринга» — это учебная модель универсального исполнителя (абстрактной вычислительной машины), предложенного в 1936 году А. Тьюрингом для уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга. Доказано, что машина Тьюринга по своим возможностям эквивалентна машине Поста и нормальным алгорифмам Маркова.

Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A={a₀,a₁,…,a_N}. Любой алфавит содержит символ «пробел», который обозначается как a₀ или Λ. При вводе команд пробел заменяется знаком подчеркивания «_».

Машина Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q={q₀,q₁,…,q_M}. В начале работы машина Тьюринга находится в состоянии q₁. Состояние q₀ — это конечное состояние: попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу a_i и некоторому состоянию q_j, находится команда, состоящая из трех частей:

1. символ из алфавита A;
2. направление перемещения: > (вправо), < (влево) или . (на месте);
3. новое состояние автомата