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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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