Составление алгоритмов для машины Тьюринга — это формирование алгоритмов для абстрактного исполнителя или абстрактной вычислительной машины.
Введение.
Машина Тьюринга может считаться одним из самых известных научных изобретений, сделанных в двадцатом веке. Она является несложной и удобной абстрактной моделью процесса вычислений, представленной в общем формате и позволяющей решать фактически весь набор компьютерных задач. Несложное описание и подробный математический анализ дают возможность причислить её к фундаментальному основанию теоретической информатики. Данное научное исследование явилось стимулом к глубокому исследованию цифровых вычислительных процессов и компьютерного оборудования, включая понимание положения о том, что есть проблема из вычислительной области, не решаемая на стандартных электронных вычислительных машинах.
Составление алгоритмов для машины Тьюринга
Алан Тьюринг намеревался описать простейшую модель механического устройства, которое обладало бы основными возможностями, изобретённых позже компьютерных устройств. Впервые Тьюринг опубликовал описание данной машины ещё в 1936-ом году в статье, названной «О вычислимых числах в приложении к проблеме разрешения», вышедшей в числе работ Лондонского математического сообщества. Машина Тьюринга являлась вычислительным устройством, состоящем из модуля сканирования, который способен считывать и записывать информацию с бумажной ленты, проходящей через него. Эта лента разделена на квадраты, которые несут по одному знаку, это или единица, или нуль. Устройство служило для ввода и вывода информационных данных и, при этом, является ещё и рабочей памятью, хранящей промежуточные итоги вычислительных операций. Машина Тьюринга состоит их следующих элементов:
- Бесконечная в двух направлениях лента, которая поделена на набор ячеек.
- Автоматический блок, представляющий собой головку сканера, считывающую и записывающую информационные данные под управлением программы. Она может находится в текущий момент времени только в одном из допустимых состояний.
Машина должна выполнять связь пары конечных информационных рядов, то есть, знаковый алфавит на входе $А = (а_0, а_1, …, а_m)$ и алфавит состояний $Q = (q_0, q_1, ..., q_p)$. При этом состояние $q_0$ определяется как пассивное, то есть, машина должна прекратить исполнение операций при считывании этого значения. Начальным состоянием считается состояние $q_1$ и машина начинает выполнение операций при считывании данного стартового состояния. Слова на ленте, являющиеся входными данными, располагаются поочерёдно по одному знаку в квадрате (позиции). Причём до него и за ним должны располагаться квадраты с нулевой информацией.
Машина Тьюринга имеет принципиальные отличия от компьютерных устройств, так как у неё запоминающим устройством является бесконечная лента. Конкретный тип задач способна решить только одна реализованная машина Тьюринга. Задачи других классов можно решить, использованием других алгоритмов. Блок управления машины должен находиться в некотором заданном состоянии и может передвигаться в любую сторону вдоль ленты. Блок управления способен записать в ячейки и сосчитать с них символы алфавита. При движении блока находится пустой элемент, который заполняет места, не содержащие входной информации.
Алгоритм машины Тьюринга реализует законы передвижения управляющего блока. Этот блок способен осуществлять следующий набор команд:
- Запись в текущую ячейку необходимого знака.
- Осуществить смену состояния, в котором находится машина.
- Выполнить перемещение блока в нужную сторону вдоль ленты.
Машина Тьюринга аналогично иным системам, разработанным для реализации вычислений, имеет определённые особенности, которые схожи со свойствами алгоритмов:
- Дискретность операций. Блок управления осуществляет перемещение к следующему этапу только после окончания обработки предшествующего этапа. Все завершённые шаги определяют, какой будет следующий за ними шаг.
- Понятность операций. Машина Тьюринга исполняет только одну процедуру в выбранной ячейке. Она прописывает символ алфавита и осуществляет одно передвижение в заданном направлении.
- Детерминированность операций. Каждой позиции в машине соответствует лишь единственный вариант реализации заданной схемы, и на каждом шаге операции и их последовательность выполнения чётко распределены.
- Результативность операций. Итоговый результат на всех шагах определяет машина Тьюринга. Программа исполняется в соответствии с заданным алгоритмом и за конечное число выполняемых шагов добирается до состояния $q_0$.
- Массовость операций. Любой из машин соответствует своя совокупность разрешённых слов, входящих в алфавит.
При осуществлении алгоритмов часто необходимо реализовать какие-либо функции. Функции могут быть алгоритмически разрешимыми или неразрешимыми, что определяется возможностью формирования вычислительной цепочки. В качестве множества натуральных или рациональных чисел, слов в конечном алфавите N для машины рассматривается последовательность множества В, то есть слова в рамках двоичного кодового алфавита В= {0,1}. Также в результат вычисления учитывается «неопределенное» значение, которое возникает при «зависании» алгоритма. Для реализации функции важно наличие формального языка в конечном алфавите и решаемость задачи распознавания корректных описаний.
Программу для машины Тьюринга необходимо формировать в виде таблицы, в которой в первой строке и столбце расположены символы внешнего алфавита и список разрешённых внутренних состояний машины, и это именуется внутренним алфавитом. Информация в таблице, по существу, является набором команд, подлежащих исполнению в машине Тьюринга. Решение задачи осуществляется согласно следующим правилам. Символ, принятый сканером из ячейки, над которой он располагается в текущий момент, и определённое внутреннее состояние сканера автомата определяют, какую команду требуется исполнить. А именно, это команда, расположенная в таблице, и находящаяся в точке пересечения знаков внутреннего и внешнего алфавита.
