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

Формализация понятия алгоритма. Машина Тьюринга.

Алгоритм — это точно определённая инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи.

Машина Тьюринга (МТ) – это математическое уточнение понятия алгоритма с помощью описания абстрактного вычислительного устройства, названного по имени английского математика Алана Тьюринга, сформулировавшего его в 1937 году, за девять лет до появления первой ЭВМ

Устройство МТ состоит из следующий частей:

• бесконечная лента, состоящая из ячеек

• головка для считывания/записи символов на ленте

• устройство управления

Бесконечная лента

Лента в машине Тьюринга состоит из ячеек, в которые можно записывать символы из заданного алфавита, а также считывать их. Если на ленте ничего не записано, то считается, что там записан специальный символ λ. Данный символ дополняет алфавит, но не входит в него явным образом.

Обычно на ленту в начале работы помещают входное слово. В процессе работы машины Тьюринга содержимое ленты модифицируется устройством управления и в результате на ленте остаётся выходное слово.

Считывающая/записывающая головка

В каждой машине Тьюринга есть специальная головка, указывающая на одну определённую ячейку на ленте. Данное устройство позволяет считывать символ с ячейки, над которой находится, или записывать символ в эту ячейку. Также головка может перемещаться влево и вправо на одну ячейку, или оставаться на месте.

Устройство управления

Под устройством управления понимается таблица состояний и правил перехода для машины Тьюринга. Состоянием называется строка таблицы, в которой в данный момент находится машина. Состояние, в котором находится машина перед запуском называется начальным, обычно обозначается именем q0. Для завершения работы МТ используется специальное терминальное состояние, которое обозначается как !.

Каждая команда состоит из трёх элементов, разделённых запятыми:
первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан).
Второй элемент – один из четырёх символов «L», «R», «N», «S».
Третий элемент – новое состояние головки после выполнения команды.
Пример команды :