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