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

Тренажер "Машина Тьюринга" - учебная модель универсального исполнителя (абстрактной вычислительной машины), предложенного в 1936 г. А. Тьюрингом для уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга. Доказано, что машина Тьюринга по своим возможностям эквивалентна машине Поста или нормальным алгоритмам Маркова.
Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита А ={а0,а1,...аN}. Любой алфавит содержит символ "пробел", который обозначается как а0 или ᴧ. При вводе команд пробел заменяется знаком подчёркивания "_".
Машина Тьюринга - автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита А, а столбцы - состояниям автомата Q= {q0,q1,...qN}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 - это конечное состояние: попав в него, автомат заканчивает работу.
В каждой клетке таблицы, соответствующей некоторому символу аi и некоторому состоянию qj, находится команда, состоящая из трех частей:
1.    Символ из алфавита А;
2.    Направление перемещения: > (вправо), < (влево) или . (на месте);
3.   Новое состояние автомата.

Используемые источники
1.    http://inf1.info/turing
2.    http://www.ict.edu.ru/ft/005970/m08-172.pdf

Энциклопедический Фонд

А

Б

В

Г

Д

Е

Ё

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я