Программирование машин Тьюринга — это программирование математической модели вычислений, определяющей абстрактную машину, которая манипулирует символами на полоске ленты в соответствии с таблицей правил.
Введение
Машина Тьюринга считается одним из самых выдающихся научных изобретений прошлого века. Она является несложной и удобной абстрактной моделью вычислительного процесса, представленной в общей форме, и обеспечивает возможность реализации фактически любой компьютерной задачи. Несложное описание и исполненный математический анализ позволили её считать основой теоретической информатики. Это научное исследование послужило стимулом к более глубокому изучению цифрового исчисления и компьютерной техники, включая осознание факта, что есть проблема в области вычислений, которую невозможно решить на стандартных электронных вычислительных машинах пользователей.
Машиной Тьюринга является чёткое математическое построение, то есть математический аппарат, который был создан для решения определенного класса задач. Данному математическому аппарату был присвоено название «машина», так как по описанию его составных частей и принципу действия он является аналогом вычислительной машины. Принципиальным отличием машины Тьюринга от вычислительных машин считается тот факт, что её устройство памяти спроектировано как бесконечная лента, а у существующих вычислительных машин запоминающий блок может иметь какие угодно большие, но обязательно конечные размеры. Машина Тьюринга не может быть реализована как раз по причине бесконечности ее ленты. С этой точки зрения она может считаться более мощной, чем любая вычислительная машина.
Программирование машин Тьюринга
В любой машине Тьюринга должны присутствовать следующие элементы:
- Бесконечная в обоих направлениях лента, которая поделена на ячейки.
- Автоматическая головка для считывания и записи информации, которая управляется программой.
Со всеми машинами Тьюринга используется пара конечных алфавитов:
- Алфавит, представляющий входные символы A = {a0, a1, ..., am}.
- Алфавит, представляющий состояния Q = {q0, q1, ..., qp}.
Необходимо отметить, что различные машины Тьюринга могут обладать разными алфавитами A и Q. Состояние q0 именуется как пассивное. Принято считать, что когда машина попадает в данное состояние, то это означает, что она окончила свою работу. Состояние q1 принято считать начальным. Именно из этого состояния, машина будет начинать свою работу.
Входное слово должно размещаться на ленте по одному символу в идущих подряд ячейках. Слева и справа от входного слова расположены лишь пустые ячейки. В алфавите А всегда должна находиться пустая буква а0, которая является признаком того, что данная ячейка пустая.
Автомат способен перемещаться вдоль ленты влево или вправо, считывать содержимое ячеек, а также выполнять запись в ячейки буквы. На рисунке ниже представлено схематичное отображение машины Тьюринга, автомат которой работает с первой ячейкой с данными:
Рисунок 1. Схематичное отображение машины Тьюринга. Автор24 — интернет-биржа студенческих работ
Автомат всё время способен «видеть» только одну ячейку. В зависимости от того, какую букву ai он увидел, а также в зависимости от своего состояния qj, автомат может исполнить следующие операции:
- Запись новой буквы в обрабатываемую ячейку.
- Осуществление сдвига по ленте на одну ячейку вправо, влево или вообще не перемещаться.
- Переход в новое состояние.
Таким образом у машины Тьюринга имеется три вида операций. Над каждой ячейкой для какой-либо пары (qj, ai) машина Тьюринга осуществляет исполнение команды, состоящей из трех операций с определенными параметрами.
Программа для машины Тьюринга является, по сути, таблицей, в каждой клетке которой расположена команда, например, как показано на рисунке ниже.
Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ
Клетка (qj, ai) может быть определена двумя параметрами, а именно, алфавитным символом и состоянием машины. Команда представляет собой набор следующих указаний:
- Куда переместить головку для чтения и записи.
- Какой именно символ подлежит записи в текущую ячейку.
- В какое состояние следует перейти машине.
Чтобы обозначить направление перемещения автомата, используется одна из следующих букв:
- «Л» означает перемещение влево.
- «П» означает перемещение вправо.
- «Н» означает неподвижность.
После исполнения автоматом текущей команды, он должен перейти в состояние qm, которое в принципе может таким же, как прежнее состоянием qj. Следующую команду необходимо искать в m-й строке таблицы на пересечении со столбцом al (букву al автомат сможет увидеть после сдвига).
Следует заметить, что когда лента содержит входное слово, то автомат расположен против какой-либо ячейки в состоянии q1. В процессе работы автомат станет перемещаться из одной клетки программы (таблицы) в другую, пока не доберётся до клетки, в которой содержится запись, что автомату следует перейти в состояние q0. Такие клетки носят название клеток останова. При достижении любой такой клетки, машина Тьюринга осуществляет остановку.
Невзирая на достаточно простое устройство, машина Тьюринга способна исполнять все возможные преобразования слов, что позволяет реализовывать различные алгоритмы.
Машина Поста также является абстрактной вычислительной машиной, которая была предложена Эмилем Леоном Постом. Она по сравнению с машиной Тьюринга имеет ещё более простую структуру, но обе эти машины по существу аналогичны и создавались для того, чтобы уточнить понятие «алгоритм».
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты. Каждая секция ленты способна быть или пустой, что отмечается нулём, или помечаться меткой единица. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние, то есть состояние ленты и позицию каретки.
