ОПИСАНИЕ МАШИНЫ ТЬЮРИНГА




МАШИНА ТЬЮРИНГА

 

 

Выполнили

 

Гаранина Наталия

Никитинская Раиса

 

 

Руководитель: Мистер Х

 

Москва 2013

 

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ. 3

ОПИСАНИЕ МАШИНЫТЬЮРИНГА.. 4

МАШИНА ТЬЮРИНГА КАК УНИВЕРСАЛЬНЫЙ ИСПОЛНИТЕЛЬ.. 7

ПРИМЕРЫМАШИНЫТЬЮРИНГА.. 8

АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ... 9

ПРИМЕРЫСОСТАВЛЕНИЯ ПРОГРАММ ДЛЯ МТ. 11

ЗАКЛЮЧЕНИЕ. 14

СПИСОК ЛИТЕРАТУРЫ... 15


ВВЕДЕНИЕ

 

Развитие теории алгоритмов начинается с доказательства К. Геделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Черча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Черча оказались эквивалентными друг другу. Основываясь на работах Геделя, С. Клини ввел понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.

В данной работе мы подробно рассмотрели абстрактный исполнитель, предложенный для формализации понятия алгоритма Аланом Тьюрингом в 1936 году. В тексте работы приводится описание машины Тьюринга, объясняется принцип ее работы, а так же дается раскрытое определение понятия универсальности исполнителя и приведены алгоритмически неразрешимые проблемы.

В приложении к реферату мы приводим примеры решения нескольких задач, реализованных на машине Тьюринга.


 

ОПИСАНИЕ МАШИНЫТЬЮРИНГА

 

Машина Тьюринга – это абстрактное вычислительное устройство, состоящее из ленты бесконечной длины, разделенной на ячейки, и каретки, которая перемещается вдоль ленты и способна читать и записывать символы. Также у машины Тьюринга есть такая характеристика, как состояние, которое может выражаться целым числом от нуля до некоторой максимальной величины. В зависимости от состояния машина Тьюринга может выполнить одно из трех действий: записать символ в ячейку, передвинуться на одну ячейку вправо или влево и установить внутреннее состояние.

Принципиальное отличие машины Тьюринга от вычислительных машин состоит в том, что ее запоминающее устройство представляет собой бесконечную ленту: у реальных вычислительных машин запоминающее устройство может быть как угодно большим, но обязательно конечным. Машину Тьюринга нельзя реализовать именно из-за бесконечности ее ленты. В этом смысле она мощнее любой вычислительной машины.

Устройство машины Тьюринга чрезвычайно просто, однако на ней можно выполнить практически любую программу. Для выполнения всех этих действий предусмотрена специальная таблица правил, в которой прописано, что нужно делать при различных комбинациях текущих состояний и символов, прочитанных с ленты.

Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм. Каждое правило предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние или переместиться на одну клетку влево или вправо. Некоторые состояния могут быть помечены как терминальные, и переход в них означает конец работы, остановку алгоритма. Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, и недетерминированной в противном случае. Конкретная машина Тьюринга задается перечислением элементов множества букв алфавита A, множества состояний Q и набором правил. Для каждой возможной конфигурации имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Необходимо указывать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

В каждой машине Тьюринга есть две части:

1) неограниченная в обе стороны лента, разделенная на ячейки;

2) автомат (головка для считывания/записи, управляемая программой).

С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов A = {a0, a1,..., am}и алфавит состояний Q = {q0, q1,..., qp}. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q.) Состояние q0 называется пассивным. Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние q1 называется начальным. Находясь в этом состоянии, машина начинает свою работу.

Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит А всегда входит пустая буква а0 — признак того, что ячейка пуста).

Автомат может двигаться вдоль ленты влево или вправо, читать содержимое ячеек и записывать в ячейки буквы. Ниже схематично нарисована машина Тьюринга, автомат которой обозревает первую ячейку с данными.

Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую букву ai он видит, а также в зависимости от своего состояния qj автомат может выполнять следующие действия:

· записать новую букву в обозреваемую ячейку;

· выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;

· перейти в новое состояние.

То есть у машины Тьюринга есть три вида операций. Каждый раз для очередной пары (qj, ai) машина Тьюринга выполняет команду, состоящую из трех операций с определенными параметрами.

Программа для машины Тьюринга представляет собой таблицу, в каждой клетке которой записана команда.

Клетка (qj, ai) определяется двумя параметрами — символом алфавита и состоянием машины. Команда представляет собой указание: куда передвинуть головку чтения/записи, какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен).

После выполнения автоматом очередной команды он переходит в состояние qm (которое может в частном случае совпадать с прежним состоянием qj). Следующую команду нужно искать в m-й строке таблицы на пересечении со столбцом al (букву al автомат видит после сдвига).

Договоримся, что когда лента содержит входное слово, то автомат находится против какой-то ячейки в состоянии q1. В процессе работы автомат будет перескакивать из одной клетки программы (таблицы) в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние q0. Эти клетки называются клетками останова. Дойдя до любой такой клетки, машина Тьюринга останавливается.

Таким образом, несмотря на свое простое устройство, машина Тьюринга может выполнять все возможные преобразования слов, реализуя тем самым все возможные алгоритмы.


МАШИНА ТЬЮРИНГА



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-07 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: