Восходит к Давиду Гильберту На рубеже 20 века сформулировал мировую проблему

Составляющие структуры

• Информационная структура алгоритма (ИСА). Структура функций есть описание конструирования функции от функций из базовых.
• Логическая структура алгоритма (ЛСА) или программы (ЛСП). ЛСА суть описание организации вычислительного процесса, который управляется состоянием памяти.

Интерпретация МТ.

• Процессор – в МТ называется управляющей головкой (УГ).
• Структура данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ
• Процесс вычислений происходит по тактам
• Процесс остановки (остановка) МТ.
• Замечание Список правил для МТ не упорядочен

МТ

• Тьюринг назвал свое абстрактное механическое устройство "универсальной машиной", поскольку она должна была справляться с любой допустимой, то есть теоретически разрешимой задачей — математической или логической.
• Данные должны были вводиться в машину на бумажной ленте, поделенной на клетки — ячейки.
• Каждая такая ячейка либо содержала символ, либо была пустой.
• Машина могла не только обрабатывать записанные на ленте символы, но и изменять их, стирая старые и записывая новые в соответствии с инструкциями, хранимыми в ее внутренней памяти.

• УУ

• таблица

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

• Представляет собой бесконечную ленту, разделенную на ячейки.
• Имеет управляющее устройство, которое перемещается в двух направлениях.
• В управляющем устройстве содержится таблица, которая описывает порядок действий.