Программа для машины ТьюрингаСтруктура машины Тьюринга Машина Тьюринга состоит из: - бесконечной в обе стороны ленты, разделенной на ячейки; - каретки (читающей и записывающей головки); - программируемого автомата. Программируемый автомат управляет кареткой, посылая ей команды в соответствии с заложенной в него сменяемой программой. Лента выполняет роль внешней памяти компьютера, автомат — роль процессора, а каретка служит для ввода и вывода данных.
Программа для машины Тьюринга Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице. Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие: Внешний алфавит. Конечное множество (обозначают буквой А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ. Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = {0, 1, а0}. Непрерывную цепочку символов на ленте называют словом. Автоматом называют устройство, работающее без участия человека. Автомат в машине Тьюринга имеет несколько состояний и при определенных условиях переходит из одного состояния в другое. Множество состояний автомата называют внутренним алфавитом. Внутренний алфавит. Конечное множество состояний каретки (автомата). Обозначается буквой Q={q1,q2...}. Одно из состояний - q1- должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние остановка. Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа. Автомат машины Тьюринга в процессе своей работы управляется программой, во время каждого шага которой выполняются последовательно следующие действия: - Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой). - Передвигаться на одну ячейку влево или вправо. - Менять свое внутреннее состояние. Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра: символ ai из выбранного алфавита A, направление перемещения каретки ("←” — влево, "→” — вправо, "точка” — нет перемещения) и новое состояние автомата qk. Например, команда 1 "←” q2 обозначает "заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.
|