3 Гёдель и Тьюринг

Вид материала

Документы

Содержание 3.20. Возможность ограничиться конечным числом-утверждений

Подобный материал:

• 17/09/2004 10: 10: 00, 54.84kb.
• Лекция: Интеллектуальные, 367.57kb.
• Доклад посвящен юбилею 55 лет назад А. Тьюринг предложил тест, ставший сегодня методологической, 19.86kb.
• Искусственный интеллект -основа новых информационных технологий, 130.05kb.
• Установочная лекция вткс, 212.41kb.
• Информационные технологии и вычислительные системы, №3, 2002, 558.37kb.

3.20. Возможность ограничиться конечным числом-утверждений

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

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

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

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

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

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

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

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

Относительно первой причины зависимостиот с отметим, что описание действительной величины числа с необходимо за­давать в явном виде только однажды (после чего внутри системы достаточно обозначения с). Если при задании величины с исполь­зуется чисто двоичное представление, то (при больших с) такое описание дает всего-навсего логарифмическую зависимость от с (поскольку количество знаков в двоичном представлении натурального п равно приблизительно). Вообще говоря, учитывая, что число с интересует нас лишь в качестве возможного предела, точное значение которого находить вовсе не обязатель­но, мы можем поступить гораздо более остроумным образом. На­пример, числоспоказателями можно задать с помощью s символов или около того, и вовсе нетрудно подыскать примеры, в которых величина задаваемого числа возрастает с ростомеще быстрее. Сгодится любая вычислимая функция от s. Иными сло­вами, для того чтобы задать предел с (при достаточно большом значении с), необходимо всего лишь несколько символов.

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

Согласимся с таким выбором с и будем в дальнейшем вме­стозаписывать. Итак,есть формальная система, теоремами которой являются все математические высказывания, какие можно вывести из конечного количества утверждений, используя стандартные логические правила (ис­числение предикатов). Количество этих -утверждений ко­нечно, поэтому разумным будет предположить, что для гарантии их действительной безошибочности вполне достаточно некото­рого набора постоянныхЕсли роботы верят в это с-убежденностью, то они, несомненно,-заключат, что гёделевское предположениетакже истинно на основании гипотезы, поскольку является П1-высказыванием меньшей, нежели с, сложности. Рассуждение для получения утвержде­нияиз-убежденности в обоснованности формальной системыдостаточно просто (в сущности, я его уже привел), так что с присвоением этому утверждению статусапроблем возникнуть не должно. То есть самотакже должно быть теоремой системы. Это, однако, противоречит убежденности роботов в обоснованности. Таким образом, упомянутая убе­жденность (при условии справедливости гипотезыи доста­точно больших числах) оказывается несовместимой с убежденностью в том, что поведением роботов действительно управляют механизмы— а значит, механизмыповедением роботов управлять не могут.

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