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

 

 

Содержание

ВВЕДЕНИЕ 3

1. 1. Машина Поста. Основные понятия и операции 4

1.2. Способ задания проблемы и формулировка 1  6

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

3.Решение Задач 11

ЗАКЛЮЧЕНИЕ 13

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

При разработке вычислительной конструкции  Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке  информации, входная информация должна быть закодирована с использованием минимального набора символов.

Несмотря на “примитивность” машины Поста, любой существующий алгоритм может быть записан в виде программы  для машины Поста. В теории алгоритмов существует так называемый “тезис Поста”: “Всякий алгоритм представим в форме машины Поста”. Этот тезис  одновременно является формальным определением алгоритма. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.

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

 

1.1. Машина Поста. Основные понятия и операции

 

Одной из фундаментальных  статей, результаты которой лежат  в основе современной теории алгоритмов является статья Эмиля Поста (Emil Post), «Финитные комбинаторные процессы, формулировка 1», опубликованная в 1936 году в сентябрьском номере «Журнала символической  логики». Пост рассматривает общую проблему, состоящую из множества конкретных проблем, при этом решение общей проблемы это такое решение, которое доставляет ответ для каждой конкретной проблемы.

Например, решение уравнения 3*х+9=0 – это одна из конкретных проблем, а решение уравнения a*x+b=0 – это  общая проблема, тем самым алгоритм (сам термин «алгоритм» не используется Постом) должен быть универсальным, т.е. должен быть соотнесен с общей  проблемой.

Основные понятия алгоритмического формализма Поста – это пространство символов (язык L) в котором задаётся конкретная проблема и получается ответ, и набор инструкций, т.е. операций в пространстве символов, задающих как сами операции, так и порядок  выполнения инструкций.

Постовское пространство символов – это бесконечная лента  ячеек (ящиков):

-

V

-

-

V

V

V

-

-

-

 

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

Пост предложил набор  инструкций (элементарных операций), которые  выполняет «работник», отметим, что  в 1936 году не было еще ни одной электронной  вычислительной машины. Этот набор  инструкций является, очевидно, минимальным  набором битовых операций:

• пометить ящик, если он пуст;
• стереть метку, если она есть;
• переместиться влево на 1 ящик;
• переместиться вправо на 1 ящик;
• определить помечен ящик или нет, и по результату перейти на одну из двух указанных инструкций;
• остановиться.

Отметим, что формулировка инструкций 1 и 2 включает защиту от неправильных ситуаций.

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

Программа (набор инструкций в терминах Поста) является одной  и той же для всех конкретных проблем, поэтому соотнесена с общей проблемой  – таким образом, Пост формулирует  требование универсальности.

Далее Пост вводит следующие  понятия:

• набор инструкций применим к общей проблеме, если для каждой конкретной проблемы не возникает коллизий в инструкциях 1 и 2, т.е. никогда программа не стирает метку в пустом ящике и не устанавливает метку в помеченном ящике;
• набор инструкций заканчивается (за конечное количество инструкций), если выполняется инструкция (6);
• набор инструкций задаёт финитный 1 – процесс, если набор применим, и заканчивается для каждой конкретной проблемы;

Финитный 1 – процесс для общей проблемы есть 1 – решение, если ответ для каждой конкретной проблемы правильный (это определяется внешней силой).

 

1.2. Способ задания проблемы и формулировка 1

 

По Посту проблема задаётся внешней силой путем пометки  конечного количества ящиков ленты. В более поздних работах по машине Поста принято считать, что  машина работает в единичной системе  счисления (0=V; 1=VV; 2=VVV; 3=VVVV), т.е. ноль представляется одним помеченным ящиком, а целое  положительное число – помеченными  ящиками в количестве на единицу  больше его значения.

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

Общая проблема называется по Посту 1-заданой, если существует такой финитный 1 – процесс, что, будучи, применим к n є N в качестве исходной конфигурации ящиков, он задает n-ую конкретную проблему в виде набора помеченных ящиков.

Если общая проблема 1-задана и 1-разрешима, то, соединяя наборы инструкций по заданию проблемы, и ее решению  мы получаем ответ по номеру проблемы – это и есть в терминах статьи Поста формулировка 1.

Эмиль Пост завершает свою статью следующей фразой: «Автор ожидает, что его формулировка окажется логически  эквивалентной рекурсивности в  смысле Геделя — Черча. Цель формулировки, однако, в том, чтобы предложить систему  не только определенной логической силы, но и психологической достоверности. В этом последнем смысле подлежат рассмотрению всё более и более  широкие формулировки. С другой стороны, нашей целью будет показать, что  все они логически сводимы  к формулировке 1. В настоящий момент мы выдвигаем это умозаключение в качестве рабочей гипотезы. … Успех вышеизложенной программы заключался бы для нас в превращении этой гипотезы не столько в определение или аксиому, сколько в закон природы».

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

АЛГОРИТМ

очевидно  <-------    гипотеза  ------->

ПРОГРАММА ПОСТА      ФОРМУЛИРОВКА 1

 

Следовательно, если гипотеза верна, то любые другие формальные определения, задающие некоторый класс алгоритмов, эквивалентны классу алгоритмов, заданных формулировкой 1 Эмиля Поста.

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

 

 

 

 

 

 

 

 

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

 

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

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

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

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

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

Формально машина Тьюринга может быть описана следующим  образом: Пусть заданы:

• конечное множество состояний – Q, в которых может находиться машина Тьюринга;
• конечное множество символов ленты – Г;

Функция (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии и обозревает символ ) в тройку декартова произведения Q х Г х {L,R} (машина переходит в состояние , заменяет символ на символ и передвигается влево или вправо на один символ ленты) – Q x Г-->Q х Г х {L,R}

• один символ из Г-->е (пустой);
• подмножество є Г --> определяется как подмножество входных символов ленты, причем е є (Г- );

Одно из состояний – є Q является начальным состоянием машины.

Решаемая проблема задается путем записи конечного количества символов из множества  є Г – Si є на ленту:
e	S1	S2	S3	S4	.........	Sn	e

 

После чего машина переводится в начальное состояние и головка устанавливается у самого левого непустого символа – , после чего в соответствии с указанной функцией переходов ( , )-->( , , L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.

Остановка машины происходит в том случае, если для пары ( , ) функция перехода не определена.

Алан Тьюринг высказал предположение, что любой алгоритм в интуитивном смысле этого слова  может быть представлен эквивалентной  машиной Тьюринга. Это предположение  известно как тезис Черча–Тьюринга. Каждый компьютер может моделировать машину Тьюринга (операции перезаписи ячеек, сравнения и перехода к  другой соседней ячейке с учетом изменения  состояния машины). Следовательно, он может моделировать алгоритмы в  любом формализме, и из этого тезиса следует, что все компьютеры (независимо от мощности, архитектуры и т.д.) эквивалентны с точки зрения принципиальной возможности  решения алгоритмических задач.