Машины Тьюринга
Общие сведения
Понятие алгоритма исторически предшествовало появлению электронно-вычислительных машин. В тысяча девятьсот тридцать шестом году математик Алан Тьюринг предложил формализацию концепции алгоритма, описав абстрактную вычислительную машину. Данная математическая модель стала фундаментальной базой для развития теории алгоритмов и последующего создания реальных вычислительных устройств. Машина Тьюринга представляет собой воображаемое устройство, оперирующее с потенциально бесконечным объемом данных. Аналогичным математическим аппаратом является машина Поста, которая концептуально близка к модели Тьюринга и также служит для формального определения алгоритма.
Теоретические основы
Машина Тьюринга рассматривается как математический аппарат, позволяющий строго определить понятие алгоритма. Поведение машины детерминировано, что является неотъемлемым свойством любого классического алгоритмического процесса. Это означает, что для каждого возможного шага вычислений при заданных исходных данных существует только одно однозначное решение. Если в ходе выполнения программы абстрактная машина не достигает конечного состояния и продолжает функционировать бесконечно, считается, что применяемый алгоритм неприменим к заданному набору начальных данных. Вычислительные процессы и решения задач с помощью данной модели всегда рассматриваются в рамках строгой бинарной логики без обращения к неопределенным бесконечным процессам как результату вычисления.
Основные определения и свойства
Конструкция машины Тьюринга включает в себя бесконечную ленту, выполняющую функцию внешней памяти, и управляющее устройство, называемое головкой или кареткой. Лента разделена на отдельные ячейки, в каждую из которых может быть записан один символ из заранее определенного конечного алфавита. Пустая ячейка формально также содержит специальный пустой символ. Головка способна перемещаться вдоль ленты, считывая содержимое текущей ячейки. На каждом дискретном шаге работы управляющее устройство воспринимает символ, при необходимости заменяет его на другой символ из того же алфавита, а затем осуществляет сдвиг на одну ячейку вправо, влево, либо остается на месте. Головка всегда находится в одном из множества возможных внутренних состояний. Состояние самой головки отождествляется с состоянием всей машины в целом, поскольку иных активных элементов модель не содержит. Существует начальное состояние, в котором система начинает работу, и специальное заключительное состояние, достижение которого инициирует остановку вычислительного процесса.
Практическое применение
Несмотря на абстрактный характер, машина Тьюринга послужила теоретической основой для разработки первых языков программирования и архитектуры реальных вычислительных систем. В сороковых годах двадцатого века на базе подобных формальных моделей начали формироваться языки ассемблера. Первоначально алгоритмы тестировались и проверялись на воображаемых машинах Тьюринга и Поста, после чего математический аппарат транслировался на аппаратный уровень физических устройств. В современной информатике программирование для машины Тьюринга используется в академических целях на профильных факультетах для изучения фундаментальных основ вычислимости. Поведение такой машины полностью определяется ее программой, в связи с чем в теоретической информатике абстрактная машина и реализующая ее программа часто отождествляются.
Особенности и характеристики
Программа для машины Тьюринга представляет собой множество команд, каждая из которых состоит из левой и правой частей. Левая часть команды содержит информацию о текущем состоянии головки и считываемом символе, выступая в роли исходных данных для конкретного такта. Правая часть определяет действия машины: записываемый символ, направление движения каретки и новое состояние. В силу детерминированности алгоритмов левые части команд в программе не могут совпадать, исключая ветвление процесса при одинаковых входных условиях. Отличительной чертой машины Тьюринга по сравнению с классическими конечными автоматами является наличие внешней, потенциально бесконечной памяти в виде ленты, содержимое которой машина способна изменять в процессе работы. Символ заключительного состояния не может выступать в качестве входных данных и фигурирует исключительно в правых частях команд, выступая меткой конца работы программы. В случае отсутствия команды для текущей конфигурации состояния и символа машина остается на месте и прекращает активные действия.