Алгоритмы и машины Тьюринга Основы алгоритмов icon

Алгоритмы и машины Тьюринга Основы алгоритмов


3 чел. помогло.
Смотрите также:
Лекция 14 (15). Размер задач и сложность алгоритмов. Временная и пространственная сложность...
Алгоритмы. История. Типы алгоритмов. Машина...
Алгоритмы и исполнители....
Методические указания к выполнению контрольных работ по дисциплине "Основы программирования"...
Учебно-методический комплекс   Специальность  010400 Информационные технологии...
Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов...
Новая модель процесса вычислений: обобщение концепции машины Тьюринга...
Лабораторная работа №1 «Алгоритмы»...
Контрольная работа №1 «Машина Тьюринга»...
Задача на использование логических операций и построение логических схем...
Программа по курсу основы информатики (алгоритмы и алгоритмические языки) по направлению 010600...
Генетические алгоритмы. Мутация (обобщенный доклад)...



Загрузка...
страницы: 1   2   3   4
вернуться в начало
скачать

Как превзойти алгоритм

К вопросу о том, как установить ис­тинность математических утверждений, мы вернемся позднее, в связи с теоремой Ге-деля (см. главу 4). Пока же я бы хотел обратить ваше внимание на то, что дока­зательство Тьюринга носит гораздо более

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

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



так что возможно в случае,

когдаСуществует немало алгоритмов типа Н(п;т). (Например, Н(п;т) мог бы просто давать на выходе 1, как толь­ко машина Тп(т) останавливается, хотя та­кой алгоритм едва ли представляет большой практический интерес!)

Мы можем повторить процедуру Тью­ринга, следуя уже пройденным путем, с той только разницей, что теперь некоторые из «» останутся не замененными на нули. Как и ранее, применив диагональный процесс, получим в качестве n-го элемента диагонали. (Мы бу­дем иметь D каждый раз, когда Отметим, что.) Это безупречно алгоритмизованное вычисление, поэтому оно может быть произведено не­которой машиной Тьюринга, скажем k-й, и тогда мы получим



Для k-го диагонального элемента (т.е. n=k)

мы имеем



Если вычисления Tk(k) останавливаются, то мы приходим к противоречию (в этом случае Н(k; k) должно равняться единице, но тогда возникнет невыполнимое равен­ство:). Значит, Tk(k) не мо­жет остановиться, т. е.



Но алгоритм не может этого «знать», потому что, если бы он давал H(k; k) = 0, мы снова пришли бы к противоречию (мы получи­ли бы тогда неверное соотношение 1 + 0=). Таким образом, если мы можем отыс­кать k, то мы знаем, как построить вы­числительную процедуру, для которой ал­горитм не дает решения проблемы оста­новки, но нам ответ известен! А как нам найти k? Это непростая задача. Необходи­мо тщательно изучить конструкцию Н(п; т) и Тп(т) и понять, как в точности действует 1 + Тn(п) х Н(п; п) в качестве машины Тью­ринга. Затем надо определить номер этой машины, который и есть k. Конечно, это выполнить трудно, но вполне возможно. Из-за этих трудностей вычисление Tk(k) нас бы вовсе не интересовало, не будь она специально предназначена для доказатель­ства неэффективности алгоритма Н! Важно то, что мы получили строго определенную процедуру, которая для любого наперед за­данного алгоритма Н позволяет найти та­кое k, что для Tk(k) этот алгоритм не мо­жет решить проблему остановки, т. е. мы тем самым превзошли его. Возможно, мысль о том, что мы «умнее» каких-то алгоритмов, принесет нам некоторое удовлетворение!

На самом деле, упомянутая процедура настолько хорошо определена, что мы мог­ли бы даже найти алгоритм для нахожде­ния k по заданному Н. Поэтому, прежде чем мы «погрязнем» в самодовольстве, мы должны осознать, что этот алгоритм мо­жет улучшить Н, поскольку он, по сути, «знает», что — или все-таки нет? В предыдущем изложении было удоб­но использовать антропоморфный термин «знать» по отношению к алгоритму. Одна­ко не мы ли в конечном счете «знаем», тогда как алгоритм просто следует опреде­ленным нами правилам? А может быть мы сами просто следуем правилам, запрограм­мированным в конструкции нашего мозга и в окружающей нас среде? Эта проблема затрагивает не только алгоритмы, но и то, как мы выносим суждения об истинности и ложности. К этим важнейшим проблемам мы вернемся позднее. Вопрос о математиче­ской истине (и ее неалгоритмической при­роде) будет рассмотрен в главе 4. На данный момент мы, по крайней мере, получили не­которое представление о значении слов «ал­горитм» и «вычислимость» и достигли по­нимания некоторых из относящихся к ним вопросов.


^ Лямбда-исчисление Черча

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

Задача о разрешимости определенной мате­матической операции может их заинтриго­вать, особенно потому, что общее решение этой головоломки само по себе алгоритми­чески не разрешимо.

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

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

В рамках этой схемы рассматривается «универсальное множество» различных объ-

ектов, обозначаемых, скажем, символами



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



мы подразумеваем, что функция b, действуя на функцию c, дает в результате другую функцию a. В рамках этой схемы нетрудно сформулировать понятие функции двух или более переменных. Если мы хотим пред­ставить, как функцию двух переменных, скажем р и q, то мы можем просто написать



(что есть результат действия функции fp на функцию q). Для функции трех перемен­ных можно использовать выражение



и так далее.

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



мы подразумеваем функцию, которая при действии на, например, a имеет значение fa, т.е



Другими словами, - это просто функция f, т.е.



Сказанное выше требует определенного осмысления. Это одна из тех математичес­ких тонкостей, которые на первый взгляд кажутся настолько педантичными и триви­альными, что их смысл часто совершенно ускользает от понимания. Рассмотрим при­мер из знакомой всем школьной математи­ки. Примем за f тригонометрическую функ­цию — синус угла. Тогда абстрактная функ­ция «sin» будет определяться выражением



(Не придавайте большого значения тому, что в качестве «функции» х может фигу­рировать величина угла. Мы скоро увидим, каким образом числа можно иногда рассма­тривать как функции, а величина угла -это просто число.) До сих пор все на самом деле тривиально. Однако представим себе, что обозначение «sin» не было изобретено, но нам известно о существовании предста­вления sin x в форме степенного ряда:



Тогда мы могли бы ввести определение




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



Тогда, например,



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



Это функция, которая, действуя на другую функцию, скажем g, дает дважды итериро­ванную g, действующую на х



Мы могли бы сначала «абстрагироваться» от ж и рассмотреть выражение



которое можно сократить до



Это и есть операция, применение которой к g дает функцию «вторая итерацияg». По сути, это та самая функция, которую Черч обозначил номером 2:



так что (2g)y = g(gy)- Аналогичным обра­зом он определил:



а также



Видно, что 2 Черча больше похоже на «два­жды», 3 — на «трижды» и т.д. Значит, дей­ствие 3 на функцию f, т. е. 3f равносильно операции «применить f три раза», поэто­му 3f при действии на у превращается в

Посмотрим, как в схеме Черча можно представить очень простую математическую операцию — прибавление 1 к некоторому числу. Определим операцию



Чтобы убедиться, что 5 действительно при­бавляет 1 к числу в обозначениях Черча, проверим ее действие на 3:




поскольку (Зb)с = b(b(bс)). Очевидно, эта операция с таким же успехом может быть применена к любому другому натуральному числу Черча. (В действительности, операция Xabc.[(ab)(bc)} приводит к тому же результа­ту, что и 5.)

А как насчет удвоения числа? Удвое­ние числа может быть получено с помощью операции



что легко видеть на примере ее действия на 3:



Фактически, основные арифметические опе­рации — сложение, умножение и возведение в степень — могут быть определены, соот­ветственно, следующим образом:



Читатель может самостоятельно убедиться (или же принять на веру), что



где т и n — функции Черча для двух на­туральных чисел, m + n — функция, выра­жающая их сумму, и т. д. Последняя из этих функций поражает больше всего. Посмо­трим, например, что она дает в случае m = 2, n = 3



Операции вычитания и деления опре­деляются не так легко (на самом деле нам потребуется соглашение о том, что делать с (т - n), когда ига меньше и, и с (m/n), когда т не делится на n). Решающий шаг в развитии этого метода был сделан в начале 1930-х годов, когда Клини удалось найти вы­ражение для операции вычитания в рамках схемы Черча! Затем были описаны и дру­гие операции. Наконец, в 1937 году Черч и Тьюринг независимо друг от друга пока­зали, что всякая вычислимая (или алгорит­мическая) операция — теперь уже в смысле машин Тьюринга - может быть получе­на в терминах одного из выражений Черча (и наоборот).

Это воистину замечательный факт, ко­торый подчеркивает глубоко объективный и математичный характер понятия вычи­слимости. На первый взгляд, понятие вычи­слимости по Черчу не связано с вычисли­тельными машинами. И тем не менее, оно имеет непосредственное отношение к прак­тическим аспектам вычислений. В частно­сти, мощный и гибкий язык программиро­вания LISP включает в себя как существен­ный элемент основные структуры исчисле­ния Черча.

Как я отмечал ранее, существуют и дру­гие способы определения понятия вычи­слимости. Несколько позже, но независимо от Тьюринга, Пост предложил во многом сходную концепцию вычислительной маши­ны. Тогда же благодаря работам Дж. Хер-бранда и Геделя появилось и более прак­тичное определение вычислимости (рекур-сивности). X. Б. Карри в 1929 году, и ра­нее, в 1924, М. Шенфинкель, предложили иной подход, который был отчасти исполь­зован Черчем при создании своего исчисле­ния (см. Ганди [1988]). Современные под­ходы к проблеме вычислимости (такие как машина с неограниченным регистром, опи­санная Катлендом [1980]) в деталях значи­тельно отличаются от разработанного Тью­рингом и более пригодны для практичес­кого использования. Однако понятие вы­числимости во всех этих подходах остается неизменным.

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


Примечания

1. Я использую обычную современную терми­нологию, в которой множество «натураль­ных чисел» включает и нуль.

2. Существует немало других известных в ма­тематике способов записи пар, троек и боль­шего количества чисел в виде одного числа, но они менее удобны для наших целей.

3. В изложенном выше я не вводил никакой метки для начала последовательности чисел (или инструкций и т. п.). Это совершен­но не требуется для входных данных, по­скольку все начинается в тот момент, когда считана первая единица. Однако для конеч­ного результата может понадобиться что-то дополнительное, поскольку априори никто не может сказать, как долго придется дви­гаться по ленте, чтобы добраться до первой (т.е. самой левой!) единицы. Хотя при дви­жении налево может встретиться длинная строка нулей, нет никаких гарантий, что еще дальше не встретится единица. В этом слу­чае применимы различные подходы. Мож­но было бы всегда использовать специаль­ную отметку (допустим, 6, записанную при помощи процедуры «сокращения»), чтобы указывать начало и завершение окончатель­ного ответа. Но для простоты я в своем из­ложении буду придерживаться другой точки зрения, согласно которой мы всегда «зна­ем», сколько в действительности ленты об­работало наше устройство (например, мож­но представить, что оно оставляет своего рода «след»), так что не обязательно про­сматривать ленту до бесконечности, чтобы убедиться в том, что весь ответ считан.

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

5. Эта процедура имеет отношение только к методу, который позволяет интерпретиро­вать запись на ленте как натуральное число. Она не изменяет номера наших конкретных машин Тьюринга, таких как EUC и XN + 1.

6. Если Тn определена некорректно, то U будет действовать так, как если бы число, отвеча­ющее п, обрывалось сразу по достижении последовательности из четырех или более единиц в двоичной записи п. Остаток вы­ражения будет считан уже как число т, после чего устройство начнет совершать не­кие бессмысленные вычисления! От этого свойства можно при желании избавиться, если представлять п в расширенной двоич­ной форме. Я решил не делать этого, чтобы еще больше не усложнять описание несчаст­ной универсальной машины Тьюринга!

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

Некоторое уменьшение величины и может быть достигнуто за счет другого определе­ния машины Тьюринга. Например, мы мог­ли бы отказаться от использования коман­ды STOP и вместо этого применять прави­ло остановки после того, как машина по­вторно возвращается во внутреннее состо­яние 0 из какого-либо другого внутренне­го состояния. Это не дало бы нам значи­тельного выигрыша (а может, и вовсе ни­какого). Большую пользу принесло бы ис­пользование лент с иными, нежели только 0 и 1, отметками. В литературе встречаются описания очень компактных на вид машин Тьюринга, но эта компактность обманчи­ва, поскольку она обусловлена чрезмерно сложным кодированием описаний машин Тьюринга вообще.

8. Желающие ознакомиться с вопросами, име­ющими отношение к этому знаменитому утверждению и изложенными без излишних технических подробностей, могут обратить­ся к работе Дэвлина [1988].

9. Мы могли бы, конечно, «обыграть» и этот модифицированный алгоритм, просто за счет повторного применения предыдущей процедуры. Тогда мы сможем использовать эти вновь полученные знания для дальней­шего улучшения алгоритма, который мы, в свою очередь, снова превзойдем; и так далее. Тип рассуждений, в который выли­вается этот повторяющийся процесс, будет рассмотрен нами в связи с теоремой Геделя в главе 4.




оставить комментарий
страница4/4
Дата16.09.2011
Размер0.61 Mb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы: 1   2   3   4
плохо
  6
не очень плохо
  1
средне
  2
хорошо
  3
отлично
  9
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх