Машина Поста и машина Тьюринга

Министерство  образования и науки РФ Федерального государственное бюджетное образовательное  учреждение Высшего профессионального  образования « Шуйский Государственный  Педагогический Университет»

 

 

 

 

 

Реферат по информатике.

Кафедра Информационных систем и технологий

Тема: «Машина  Поста и машина Тьюринга»

 

 

 

 

 

 

 

 

 

 

Работу  выполнила студентка ТФ 1-2

Гонохина  Екатерина Андреевна

Работу  проверила:  Голубева Светлана Константиновна

 

 

 

 

 

2012 год.

Содержание:

 

1. Машина Поста…………………………………………. 3
1. Введение…………………………………………....
2. Принцип работы…………………………………..
3. Объекты используемые в программе…………..
4. Функции используемые в программе…………..
5. Варианты окончания выполнения программы на машине Поста…………………………………………………...
6. Пример работы машины Поста…………………

 

2. Машина Тьюринга…………………………………….. 9
1. Введение…………………………………………….
2. Описание машины Тьюринга…………………....
3. Свойства машины Тьюринга как алгоритма….
4. Сложность алгоритмов……………………………
5. Сложность проблем………………………………..
6. Машина Тьюринга и алгоритмически неразрешимые проблеммы…………………………………….
7. Заключение…………………………………………
8. Пример работы машины Тьюринга…………….

 

 

            3.        Список используемой  литературы……………………......20

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Машина Поста 

 

       1.1 Введение

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы. 
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

 

1.2 Принцип работы

Машина  Поста состоит из каретки (или  считывающей и записывающей головки) и разбитой на секции бесконечной  в обе стороны ленты. Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг  каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа  строк. Всего команд шесть: N. → J сдвиг вправо N. ← J сдвиг влево N. 1 J запись метки N. 0 J удаление метки N.  ? J1, J0 если в ячейке 1, то перейти к j1 строке программы, иначе перейти к j0 строке. N. Stop остановка

N. — номер  строки, J — строка на которую  переходит управление далее.

Для работы машины нужно задать программу  и ее начальное состояние (т. е. состояние  ленты и позицию каретки). После  запуска возможны варианты: работа может закончиться невыполнимой командой (стирание несуществующей метки  или запись в помеченное поле); работа может закончиться командой Stop; работа никогда не закончится.

1.3 Объекты используемые  в программе

• Memo-это текстовое поле с возможностью построчного считывания и зиписи. Используется для исходного текста программы и для демонстрации интерпетированного кода в его пошаговом исполнении.
• Edit- это текстовое поле с возможностью считывания и зиписи, в полях этого типа храняться: исходная лента машины Поста, ее текущее состояние, и информация о работе программы
• Button- кнопки, запускает определенные наборы функций и команд к выполнению

 

1.4 Функции используемые  в программе

• Char shag(void) Обработка одной текущей команды машины Поста. Сдвигает каретку, снимает или ставит метку, осуществляет условный переход. Возвращает код ошибки: 0-нет ошибки -1-переход на команду меньше нуля -2 попытка перехода на команду больше максимального числа команд -3 попытка снять метку где ее нет -4 попытка установить метку где она есть Если получает символ остановки "S" то возвращает 0, по командам не сдвигается
• void print_sostoyanie(int i) отображает состояние машины поста(Memo2), включая текушую команду(показана "*"), текущее состояние ленты с позицией каретки(Edit2), а также результаты выполнения последней команды(Edit4) и показывает нормальное завершение программы на языке машины поста. i-тип результата последней команды. Если i=: 1- начальное состояние(произведена инициализация и не одной команды не выполнилось) -2 попытка перехода на команду больше максимального числа команд -3 попытка снять метку где ее нет -4 попытка установить метку где она есть 0 программа выполняется
• void fastcall TForm1::Button1Click(TObject *Sender) Обработчик нажатия кнопки "c начала". Производит полный разбор и инициализацию данных (позиция каретки, создает массив данных ленты,получает массив команд во внутреннем представлении из текста). Запускает функцию print_sostoyanie(1)
• voidfastcall TForm1::Button2Click(TObject *Sender) Выполнение одного шага и обновление данных, вызывает функции:shag, print_sostoyanie.
• void fastcall TForm1::Button3Click(TObject *Sender) Выполняет m шагов начиная с последнего, количество выполняемых при нажании этой кнопки шагов берется из Edit3. Обновляются данные на формах принт начала программы

 

Машина Поста состоит из:

• бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),
• головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.

Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:i K j,

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для  машины Поста существует шесть типов  команд:

1. V j - поставить метку, перейти к j-й строке программы.
2. X j - стереть метку, перейти к j-й строке программы.
3. <- j - сдвинуться влево, перейти к j-й строке программы.
4. -> j - сдвинуться вправо, перейти к j-й строке программы.
5. ? j₁; j₂ - если в ячейке нет метки, то перейти к j₁-й строке программы, иначе перейти к j₂-й строке программы.
6. ! – конец программы (стоп).

У команды «стоп» отсылки нет.

1.5 Варианты окончания выполнения  программы на машине Поста:

1. Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.
2. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).
3. Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число  команд, чем аналогичные программы  для машины Тьюринга. 
Почему достаточно лишь два различных символа (есть метка, нет метки)? Дело в том, что любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита.

       1.6 Пример работы машины Поста:

Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4). 
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д. 
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так: 
1. -> 2 
2. ? 1;3 
3. <- 4 
4. V 5 
5. ! 
А процесс выполнения может быть таким:

 

 

 

 

 

Алгоритм  для машины Поста:

1. Сдвинуть каретку влево. Перейти к команде 2.
2. Обозревать ячейку. Если в ячейке нет метки - перейти к команде 1. Иначе - к команде 3
3. Сдвинуть каретку вправо. Перейти к команде 4.
4. Записать метку. Перейти к команде 5.
5. Остановиться.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Машина Тьюринга

 

2.1 Введение

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

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

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

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

 

2.2 Описание машины Тьюринга

Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью "О вычислимых числах в  приложении к проблеме разрешения", которая наравне с работами Поста  и Черча лежит в основе современной  теории алгоритмов.

Предыстория создания этой работы связана с формулировкой  Давидом Гильбертом на Международном  математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача доказательства непротиворечивости системы  аксиом обычной арифметики, которую  Гильберт в дальнейшем уточнил как "проблему разрешимости" - нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики.

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

Приведем  характеристику этой работы, принадлежащую  Джону Хопкрофту: "Работая над  проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия  метода. Отталкиваясь от интуитивного представления о методе как о  некоем алгоритме, т.е. процедуре, которая  может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно  воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной  впоследствии машиной Тьюринга".

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

Формально машина Тьюринга может быть описана следующим  образом. Пусть заданы:конечное множество  состояний – Q, в которых может  находиться машина Тьюринга;конечное множество символов ленты – Г;функция  δ (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии qi и обозревает символ gi) в тройку декартова произведения Q х Г х {L,R} (машина переходит в  состояние qi, заменяет символ gi на символ gj и передвигается влево или  вправо на один символ ленты) – Q x Г-->Q х Г х {L,R}один символ из Г-->е (пустой);подмножество Σ є Г - -> определяется как подмножество входных символов ленты, причем е  є (Г - Σ);одно из состояний – q0 є Q является начальным состоянием машины.