Теория автоматов Машины Тьюринга




НазваниеТеория автоматов Машины Тьюринга
Дата конвертации26.05.2013
Размер445 b.
ТипПрезентации


Теория автоматов

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


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

  • Конечные автоматы — как преобразователи входных последовательностей сигна­лов, так и распознаватели множеств цепочек — выполняют преобразование вход­ной информации в соответствии с некоторыми правилами, то есть реализуют не­который алгоритм переработки информации. Иными словами, автоматы — это ус­тройства, механически выполняющие алгоритмы. Можно строить различные мо­дели устройств, автоматически выполняющих алгоритмы, и исследовать классы алгоритмов, которые могут быть реализованы на этих моделях



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

  • Алгоритм является фундаментальной концепцией информатики, и вопросы по­строения автоматических устройств, реализующих алгоритмы, — это один из глав­ных вопросов вычислительной науки. Какой класс алгоритмов может быть пред­ставлен конечными автоматами, независимо от числа состояний автоматов, их фун­кций переходов и выходов? Поставим вопрос по-другому. Можно ли для любого алгоритма переработки информации найти конечный автомат, его выполняющий? Ведь число различных конечных автоматов бесконечно



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

  • Очевидно, что ответом здесь будет «нет». Конечные автоматы могут решать толь­ко узкий класс алгоритмических проблем. Конечный автомат как автоматическое устройство, перерабатывающее информацию, ограничен в своих возможностях. Например, мы уже знаем, что никакой КА не может решить проблему умножения двух чисел, с помощью КА невозможно распознать язык {an b cn | n > 0}. Иными сло­вами, не все алгоритмы обработки информации могут быть реализованы конечны­ми автоматами. Класс алгоритмов, которые могут быть реализованы конечными автоматами, весьма ограничен.



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

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

  • Q получить общее представление об алгоритмах и методах их формального пред­ставления;

  • Q научиться представлять простейшие алгоритмы в виде программы для маши­ны Тьюринга;

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



Формальные модели алгоритмов

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

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



Формальные модели алгоритмов

  • Это определение, понятное в интуитивном смысле, не является, однако, формаль­ным. Действительно, что означает «элементарная операция»? Или «предписание»? С какими объектами работает алгоритм: числами, матрицами, словами?... Все это требует уточнения, если мы хотим говорить об алгоритмах строго. Алгоритмы в интуитивном смысле не являются математическими объектами, к ним не приме­нимы формальные методы исследования и доказательства. Поэтому в XX веке были предприняты усилия в попытках формализации понятия алгоритма. Формализа­ция понятия алгоритма необходима по разным причинам. Например, сравнение двух алгоритмов по эффективности, проверка их эквивалентности и т. д. возмож­ны только на основе их формального представления



Формализация понятия алгоритма

  • Впервые необходимость формального понятия алгоритма возникла в связи с про­блемой алгоритмической неразрешимости некоторых задач. Долгое время мате­матики верили в возможность того, что все строго поставленные математические задачи могут быть алгоритмически решены, нужно только найти алгоритм их ре­шения. Вера в универсальность алгоритмических методов была подорвана рабо­той Курта Геделя (1931 год), в которой было показано, что некоторые математи­ческие проблемы не могут быть решены с помощью алгоритмов из некоторого класса



Формализация понятия алгоритма

  • . Этот класс алгоритмов определяется некоторой формальной конкретизацией понятием алгоритма. Встал вопрос: являются ли алгоритмически неразрешимыми эти проблемы только в рамках использованной Геделем модели алгоритма или же для решения этих проблем вообще нельзя придумать никакого алгоритма ни в ка­ком смысле? Общность результата Геделя зависит от того, совпадает ли использо­ванный им класс алгоритмов с классом всех алгоритмов в интуитивном смысле. Поэтому поиск и анализ различных уточнений и формализации алгоритма и соот­ношение этих формализации с интуитивным понятием алгоритма является прак­тически важным.



Формализация понятия алгоритма

  • К настоящему времени предложен ряд формальных моделей алгоритма. Курт Ге-дель определил алгоритм как последовательность правил построения сложных математических функций из более простых, Алонзо Черч использовал формализм, называемый А-исчислением, Алан Тьюринг предложил гипотетическое автомати­ческое устройство, которое сейчас называется машиной Тьюринга, и определил алгоритм как программу для этой машины, А. А. Марков определил алгоритм как конечный набор правил подстановок цепочек символов и т. д.



Формализация понятия алгоритма

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



Формализация понятия алгоритма

  • На основании этих результатов в информатике получило признание следующее положение: «Любое разумное определение алгоритма, которое может быть пред­ложено в будущем, окажется эквивалентным уже известным определениям», что означает, по сути, предположение об адекватности понятий алгоритма в интуи­тивном смысле и алгоритма в точном смысле в одном из перечисленных эквивалент­ных формализмов. Это положение в настоящее время широко используется в каче­стве гипотезы, обоснованной в силу того, что не удалось найти противоречащих ей примеров. Эту гипотезу, однако, невозможно доказать строго, поскольку понятие алгоритма в интуитивном смысле является неформальным.



Формализация понятия алгоритма

  • Исторически Алонзо Черч первый предложил отождествить интуитивное поня­тие алгоритма с одним из эквивалентных между собой точных определений. Алан Тьюринг независимо высказал предположение, что любой алгоритм в интуитив­ном смысле может быть представлен машиной Тьюринга (а значит, и в любой дру­гой эквивалентной форме). Это предположение известно как тезис Черча-Тъю-ринга. Тезис Черча-Тьюринга просто отражает нашу уверенность в том, что разра­ботанные формальные модели алгоритма достаточно полно представляют наше интуитивное его понимание.



Формализация понятия алгоритма

  • Тезис Черча-Тьюринга имеет важное практическое значение. Например, поскольку каждый компьютер (с потенциально бесконечной памятью) может моделировать машину Тьюринга (см. пример 5.3) и, следовательно, алгоритмы в любом другом формализме, то из этого тезиса следует, что все компьютеры, как маленькие персо­нальные компьютеры, так и большие суперкомпьютеры, эквивалентны с точки зре­ния принципиальной возможности решения алгоритмических проблем.

  • Определение машины Тьюринга среди других эквивалентных определений кажется наиболее удобным для формального определения понятия алгоритма.



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

  • По сути своей, алгоритм есть механический процесс обработки информации. Впер*"* вые Алан Тьюринг определил понятие алгоритма исходя из понятия автоматичес­ки работающей машины; более того, он предложил формальную модель такого ус­тройства, которое интуитивно моделирует действия человека, решающего задачу, руководствуясь некоторым алгоритмом. Это устройство было названо машиной Тьюринга. Как оказывается, машина Тьюринга является весьма простым расши­рением модели конечного автомата.



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

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



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

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



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

  • Рассмотрим, чем отличается машина Тьюринга от простой модели конечного ав­томата. Конечный автомат можно представить себе как устройство с конечным числом внутренних состояний, работающее с двумя лентами: входной и выходной (рис. 5.1). Конечный автомат работает по тактам. На каждом такте он читает с по­мощью некоторой входной головки символ из обозреваемой ячейки входной лен­ты, изменяет свое состояние и печатает некоторый символ выходного алфавита в обозреваемую ячейку выходной ленты, после чего две его головки чтения и залисм перемещаются на одну позицию вправо. Описание функционирования конечного



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

  • автомата можно считать его программой: в ней просто перечислено конечное чис­ло четверок (команд) , где s — текущее состояние, а — очередной вход­ной сигнал, р — следующее состояние и у — очередной выходной сигнал. Програм­ма КА — это просто перечисление аргументов и соответствующих результатов ча­стично-определенной функции переходов и выходов автомата б: SxX—>SxY.

  • Рис. 5.1. Сравнение определений машины Тьюринга и конечного автомата

  • В своем вычислительном устройстве Тьюринг смоделировал доведенный до са­мых элементарных операций процесс выполнения произвольного алгоритма че­ловеком. Человек имеет конечную память, и в этом смысле его можно представить системой с конечным числом состояний. Исходная информация к алгоритму обыч­но представляется в виде цепочки символов.



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

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



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



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

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



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

  • Машина Тьюринга работает по тактам. На каждом такте она читает символ из обо­зреваемой ячейки рабочей ленты, изменяет свое состояние в зависимости от свое­го внутреннего состояния и прочитанного символа и печатает символ в обозревае­мую ячейку рабочей ленты, после чего ее головка чтения-записи может перемес­титься на одну позицию влево, вправо или остается на месте. Описание функцио­нирования МТ можно считать ее программой, которая представлена конечным набором пятерок (команд) < s, а, р, у, D >, где s, a, p и у имеют тот же смысл, что и в конечном автомате, a D — направление перемещения головки по рабочей ленте, которое может быть одним из трех значений: L — влево, R — вправо и Н — оста­ваться на месте.



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

  • . Иными словами, программа МТ — это просто конечный список пятерок, представляющих собой аргументы и соответствующие им результаты частично-определенной функции переходов и выходов 5: SxX—>8хХхГ.

  • Машина Тьюринга имеет один конечный рабочий алфавит X, в котором входные и выходные символы не различаются: выходной символ, напечатанный на ленте, машина может прочитать в последующих тактах. Для удобства обычно считают, что X содержит пустой символ Л, находящийся во всех ячейках рабочей ленты слева и справа от конечной цепочки «значащих» символов в начале работы.



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

  • Машина Тьюринга имеет один конечный рабочий алфавит X, в котором входные и выходные символы не различаются: выходной символ, напечатанный на ленте, машина может прочитать в последующих тактах. Для удобства обычно считают, что X содержит пустой символ Л, находящийся во всех ячейках рабочей ленты слева и справа от конечной цепочки «значащих» символов в начале работы.

  • Рассмотрим, как работает машина Тьюринга. Конфигурацией машины Тьюринга называется ее текущее состояние, текущее состояние рабочей ленты и место рас­положения головки. При работе МТ в каждом такте происходит смена конфигура­ций. Пусть МТ находится в состоянии s и в обозреваемой ячейке ленты находится символ а.



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

  • . Если в программе МТ нет команды для пары , то МТ останавлива­ется. Если в программе МТ несколько команд для данной пары a>, то это — недетерминированная машина Тьюринга, в ней выполняется одна из нескольких возможных команд с левой частью . Очевидно, что в любой момент работы на ленте МТ находится только конечная цепочка «значащих» символов. После останова машины Тьюринга эта цепочка является результатом переработки вход­ной цепочки. Таким образом, МТ является автоматом-преобразователем символь­ных цепочек.



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

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

  • Машина Тьюринга информация на рабочей ленте является результатом переработки входной информации. "••<•*-'•



Похожие:

Теория автоматов Машины Тьюринга iconТеория автоматов Машины Тьюринга
Если в заключительном состоянии останавливается машина-преобразователь Машина Тьюринга информация на рабочей ленте является результатом...
Теория автоматов Машины Тьюринга iconУчебник по математической логике и теории вычислимости. Августа Ада Лавлейс (1815 1852)
Алана Тьюринга хорошо знакомо еще со студенческой скамьи: всем им приходилось изучать "машину Тьюринга" "основу основ" теории ал­горитмов....
Теория автоматов Машины Тьюринга iconЛекции лекция 1
Предмет теория автоматов введет в курс и даст начальные представления о: важнейших классических основных моделях автоматов
Теория автоматов Машины Тьюринга iconТеория автоматов Основные понятия, способы задания, типы автоматов
Последовательности выходных символов (y1[1]y2[2]y3[3] ) для последовательности символов (x1[1]x2[2]x3[3] ) разворачиваются в моменты...
Теория автоматов Машины Тьюринга iconТеория и практика многопоточного программирования
Использование конечных автоматов для разработки и анализа неблокирующих алгоритмов
Теория автоматов Машины Тьюринга iconТеорема Если язык L принимается многоленточной машиной Тьюринга, то он принимается одноленточной машиной Тьюринга. Теорема 2

Теория автоматов Машины Тьюринга iconТеория Автоматов Конечные функциональные преобразователи
Семантическое дерево это двоичное дерево, корень которого помечен двоичной функцией от m переменных, из каждого узла идут по два...
Теория автоматов Машины Тьюринга iconЛекция 3 Функциональные модели автоматов. 6 Функциональные модели автоматов
Для представления функционирования модели автомата необходимо представить модель вх/вых переменных
Теория автоматов Машины Тьюринга iconТеория Автоматов Конечные функциональные преобразователи
Решение проблемы нахождения любых других базисов булевых функций, отлич­ных от указанных в табл. 5, было найдено Эмилем Постом в...
Теория автоматов Машины Тьюринга iconТеория автоматов Конечные автоматы
Из примера 2 видно, что разные автоматы могут функционировать одинаково, даже если у них разное число состояний. Важной задачей является...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница