Машина Тьюринга — это абстрактная вычислительная модель, которая манипулирует символами на ленте.Формально машина Тьюринга состоит из бесконечной ленты, разбитой на ячейки, каждая содержит символ из конечного алфавита; управляющего устройства с конечной памятью состояний; и головки, способной считывать, писать и сдвигаться на одну ячейку. Функция переходов определяет по текущему состоянию и считанному символу новый символ, направление сдвига (Л/П) и новое состояние. Машина начинает работу с входным словом на ленте и может остановиться в принимающем или отвергающем состоянии, либо застрять в бесконечном цикле. Универсальная машина Тьюринга может моделировать любую другую по её описанию — предвосхищение концепции программируемого компьютера.
В 1936 году Алан Тьюринг, решая Entscheidungsproblem (проблема разрешения) Давида Гильберта, ввёл понятие «a-машины» (автоматической машины) в статье «On Computable Numbers». Его цель была — формализовать интуитивное понятие алгоритма. Независимо Алонзо Чёрч пришёл к эквивалентному понятию λ-исчисления. Тезис Чёрча-Тьюринга утверждает, что любой интуитивно вычислимый процесс реализуем на машине Тьюринга. В 1945 году Джон фон Нейман использовал эту модель в архитектуре EDVAC — прообразе современных компьютеров. В 1985 году Дэвид Дойч предложил квантовую машину Тьюринга, открыв путь квантовым вычислениям.
Машина Тьюринга вычисляет, манипулируя строками символов. Алгоритмически она эквивалентна языку программирования с одним массивом бесконечной длины. Ключевые свойства: существование универсальной машины (интерпретатор), неразрешимость проблемы остановки (нельзя алгоритмически определить, остановится ли произвольная машина на данном входе), теорема о рекурсии (машина может получить собственное описание). В теории сложности рассматриваются оракульные машины (с дополнительной информацией) и вероятностные машины (с датчиком случайных битов). Квантовые машины Тьюринга оперируют состояниями в гильбертовом пространстве и используют унитарные преобразования; они не нарушают тезис Чёрча-Тьюринга, но могут давать экспоненциальное ускорение для некоторых задач.
Любая компьютерная программа — от калькулятора до ассистента с ИИ — сводится к инструкциям, которые может выполнить машина Тьюринга. На ней основана вся теория вычислений.
Простейшая универсальная машина Тьюринга, придуманная Марвином Минским, использует всего 7 состояний и 4 символа — и всё равно способна вычислить всё, что может мощный суперкомпьютер, хотя и чудовищно медленно.










