Дуглас Р. Хофштадтер
Перевод А. Семенова
Г Л А В А I
MU-головоломка
Формальная Система
Центральным понятием этой книги является формальная система. Формальная система, которую я буду далее использовать, была изобретена в 20-х годах американским логиком Эмилем Постом, и ее часто называют "порождающая система Поста". Эта глава познакомит вас с этой формальной системой и, кроме того, я очень надеюсь, у вас возникнет желание хоть немного ее исследовать. Поэтому для разжигания вашего интереса я изложу небольшую загадку.
Загадка в следующем: "Можете ли вы получить MU?"* Для начала вы будете снабжены цепочкой символов. Чтобы не держать вас в темноте, скажу сразу, что это цепочка символов - MI. Далее будут разъяснены некоторые правила, по которым вы можете заменять одну цепочку символов на другую. Если одно из этих правил применимо к выбранной цепочке, и вы хотите его применить, то можете это сделать. Но нет ничего такого, что бы вам диктовала какое конкретно правило надо применять, если вы окажетесь на распутье, и вам придется выбором из нескольких одинаково допустимых вариантов. Этот выбор остается за вами. И конечно этот выбор превращает ограниченную формальными рамками игру в нечто похожее на искусство.
Главный момент, который почти не нуждается в объяснении, это то, что вы не должны делать чего-либо, что не оговорено в правилах. Мы могли бы назвать это ограничение "Требованием Формальности". В главе с названием "Формальная система", наверное, это "правило" вряд ли стоило подчеркивать особо. Однако, хотя это звучит странно, я предсказываю, что как только вы начнете играть с предложенной здесь системой, вы нарушите Требование Формальности много раз, если, конечно, вы не работали с формальными системами прежде.
* В этой книге, мы будем придерживаться следующего соглашения, когда обращаем ваше внимание на цепочки символов. Если цепочки пишутся так, что их тяжело отличить от текста предложения, то они будут взяты в единичные или двойные кавычки. Пунктуация, которая принадлежит предложению, а не цепочке, будет идти за пределами кавычек, как это диктует логика. Например, первая буква этого предложения - Н, в то время как первая буква ' этого предложения. ' - ' э '. Однако, кавычки будут обычно опускаться, если все ясно и без них. Например, первая литера квадрата - к.
Первое, что следует сказать о нашей формальной системе, MIU-системе, состоит в том, что она использует всего три буквы латинского алфавита: M, I и U (эти три буквы так и называют: а л ф а в и т системы –прим. А.С). Это значит, что цепочки символов в MIU-системе - это только те цепочки, которые составленные из этих трех букв. Вот некоторые примеры таких цепочек:
MU
UIM
MUUMUU
UIIUMIUUIMUIIUMIUUIMUIIU
И хотя все эти цепочки вполне допустимы, они не являются теми цепочками, которые "находятся в вашей власти" или "собственности". Фактически, единственная пока принадлежащая вам цепочка- цепочка MI. И только используя правила, которые сейчас будут представлены, вы можете пополнить вашу собственную коллекцию новыми цепочками.
Вот первое правило:
Правило I: Если вы имеете цепочку символов, последний символ которой - I, вы можете прибавить к ней в конец символ U.
Отмечу, между прочим (если вы до этого момента не задумывались о значении термина "цепочка"), что цепочка предполагает, расположение символов в определенном порядке. Например, MI и IM - две различные цепочки. Учтите, это не просто "мешочек" с символов, в который те свалены кучей, и их порядок не имеет значения.
Теперь второе правило:
Правило II: Предположим, что вы имеете Mx, тогда вы можете добавлять Mxx к вашей коллекции.
Что под этим подразумевается, я покажу на примерах ниже:
Из MIU, вы можете получить MIUIU.
Из МUM, вы можете получить MUMUM.
Из MU, вы можете получить MUU.
Литера 'x' в правиле ставится вместо любой подцепочки символов. Но как только вы решите, какая это подцепочка, вы должны четко придерживаться этого выбора (пока вы не используете это правило в следующий раз, где вы будете делать новый выбор). Обратите внимание на третий из приведенных выше примеров. Он показывает как вы, однажды получив MU, можете получать из нее другую цепочку символов для пополнения вашей коллекции. Но прежде вы непременно должны получить MU!
Я хочу добавить последний комментарий относительно символа 'x'. Этот символ не является частью формальной системы, таким же, как литеры M, I и U. Но, тем не менее, он полезен нам, ибо позволяет говорить о подцепочках символов вообще. Задача символа 'x' - стоять за произвольную последовательность символов в преобразуемой цепочке. Но если вы когда-нибудь добавите к вашей коллекции цепочку, содержащую сам символ 'x' , то вы сделает что-то неправильно. Потому что цепочки MIU-системы никогда не содержат символ 'x'.
Имеется третье правило.
Правило III: Если подцепочка III встречается в какой-либо цепочке вашей коллекции, то вы можете получить новую цепочку подставляя символ U на место III.
Например:
Из UMIIIMU, вы можете получить UMUMU.
Из MIIII, вы можете получить MIU (или MUI).
Из IIMII, вы не можете ничего получить, используя это правило. (Три I должны стоять последовательно)
Из MIII, получается MU.
Я очень надеюсь, что вас не посетит идея применять это правило в обратную сторону. Например, так:
Из MU, получается MIII. < = Это неверно!
Все правила односторонние.
Наконец имеется последнее правило.
Правило IV: Если подцепочка UU встречается внутри одной из ваших цепочек, вы можете исключить ее.
Из UUU, получится U.
Из MUUUIII получится MUIII
Теперь мы имеем все, что нам необходимо, и вы можете попробовать получить MU. Не волнуйтесь, если вы не достигните успеха. Просто попробуйте немного. Главное для вас сейчас - почувствовать вкус MU-головоломки.
Теоремы, Аксиомы, Правила
Ответ на MU-головоломку появиться в книге позже. Пока важно не найти ответ, а сам поиск ответа. Вы, надеюсь, сделали несколько попыток получить MU. Совершая эти попытки, вы получили собственную коллекцию цепочек. Такие цепочки символов, получаемые по правилам, называются теоремами. Конечно, термин "теорема" обычно применяется в математике, которая весьма отличается оттого, что мы тут выстроили. "Теорема" - это утверждение на обычном языке, истинность которого доказывается строгим логическим способом, типа Теоремы Зенона относительно "не существования" движения, или Теоремы Евклида о бесконечности множества простых чисел. Но в формальных системах о теоремах нельзя думать как об утверждениях. Здесь теоремы- цепочки символов. Вместо того, что бы быть самодостаточными истинами, наши теоремы как будто произведены машиной, согласно некоторым типографским правилам. Чтобы в дальнейшем подчеркивать это важное различие в значениях термина "теорема", я в этой книге приму следующее соглашение: когда "теорема" пишется с заглавной буквы, ее значение будет каждодневным. Теорема - утверждение на обычном языке, которое кто-то, когда-то доказал как истинное утверждение с помощью строгих аргументов. Если же "теорема" пишется с маленькой буквы, то имеется в виду техническое значение: это цепочка символов, полученная механически в некоторой формальной системе. В этом смысле MU-головоломка звучит так: является ли MU теоремой MIU-системы?
Для того, что бы с чего-то можно было начать, я дал вам одну "свободную" цепочку, а именно MI. Такая свободная теорема называется аксиомой - термин, техническое значение которого здесь, так же весьма далек от общеизвестного. Формальная система может иметь ноль, одну, несколько или даже бесконечное число аксиом. Примеры всего этого мы еще встретим на протяжении нашей книге.
Каждая формальная система имеет правила для соединения символов типа вышеприведенных четырех правил MIU-системы. Они называются или правилами доказательства или правилами вывода. Я буду использовать оба термина.
И последний термин, который я хочу представить в этом разделе - вывод.
Ниже показано, как выведена теорема MUIIU:
(1) MI ........................... Аксиома
(2) MII .......................... Из (1) в соответствии с правилом II
(3) MIIII ....................... Из (2) в соответствии с правилом II
(4) MIIIIU .................... Из (3) в соответствии с правилом I
(5) MUIU ...................... Из (4) в соответствии с правилом III
(6) MUIUUIU ............... Из (5) в соответствии с правилом II
(7) MUIIU ..................... Из (6) в соответствии с правилом IV
Вывод теоремы показывает явно, шаг за шагом, как получается искомая теорема из аксиомы согласно правилам формальной системы. Понятие вывода идентично понятию доказательства, но вывод - нам пока кажется только ближайшим братом доказательства. Ведь звучало бы странно, что вы доказали MUIIU, но не столь странно звучит, что вы вывели MUIIU.
Внутри и снаружи Системы
Большинство людей, приступив к решению MU-головоломки, производят наугад множество теорем только для того, что бы посмотреть, что из этого получиться. Довольно скоро они начинают замечать некоторые свойства тех цепочек, которые получили. Это то, что человеческий интеллект обычно схватывает мгновенно. Например, возможно, это сразу не было очевидным, что все теоремы системы начинаются с символа M. Но вскоре вы увидели это на множестве примеров. Со временем обозначилась общая закономерность и мало того, что вы могли заметить ее, вы могли понять ее справедливость. Приглядевшись к правилам, вы могли сообразить, что каждая новая теорема наследует первую букву от более ранней теоремы. В итоге получается, что первый символ всех теорем были унаследованы от первого символа единственной аксиомы MI и это доказывает, что все теоремы MIU-системы должны начинаться с символа M.
Из всего этого возникает важный вывод. Вышесказанное демонстрирует одно различие между людьми и машинами. У нас есть возможность построить (фактически это очень легко сделать) компьютерную программу, которая бы непрерывно строила теоремы MIU-системы, и мы могли бы включить в программу команду, которая бы останавливала процесс только после того, как будет получена строка U. Теперь вы знаете, что компьютер, так запрограммированный, никогда не остановится. И это вас не удивляет. Но что будет, если вы попросите друга получить U? Вас нисколько не удивит, если друг через некоторое время вернется и заявит вам, что нет никакого способа избавиться от символа M в начале всех цепочек и поэтому решать вашу задачу - что воду в ступе толочь. Даже если человек не очень сообразителен, он все равно не может оставить без внимания подозрительную закономерность и, в конце концов, у него накопится интуитивное недоверие к задаче - это та интуиция, которой компьютерной программе, как мы ее описали, не хватает.
Теперь позвольте мне более точно объяснить, что я имел в виду говоря, мол, покажу разницу между человеком и машиной. Я полагаю вполне возможным, чтобы программируемая машина выполняла рутинную задачу таким способом, что она никогда не будет замечать даже очевидные факты относительно, того, что делает, но это невозможно для человеческого сознания - не замечать некоторые факты относительно того, что он делает. Вы это прекрасно понимаете. Если вы наберете на клавишах счетной машинки "1", а потом прибавляете к этому 1, и затем прибавите 1 снова, снова и снова, и так будете продолжать в течении многих часов, то счетный механизм никогда не научится повторять ваши действия и делать эту операцию уже непосредственно без вас, хотя любой человек приобрел бы подобный механический навык очень быстро. Или, возьмем глупый пример. Автомобиль никогда не приобретет собственных навыков (не зависимо от того, как хорошо и как долго его водили) для того, чтобы избегать другие автомобилями или препятствиями на дороге, и он никогда не обучится самостоятельно ездить даже по тем маршрутам, где очень часто ездили вместе с хозяином.
Коренное различие в том, что действовать совершенно без внимания - для машины вполне возможно, но совершенно невозможно для человека. Замете, я не говорю, что все машины обязательно не способны к глубоким наблюдениям. Нет, только некоторые машин. И при этом я не говорю, что все люди всегда делают тонкие наблюдения. Люди, как правило, очень часто оказываются вопиюще невнимательными. Но машины могут быть сделаны так, что бы действовать абсолютно невнимательно, а люди на такое не способны. И пока большая часть машин, хотя выглядят они довольно симпатично, сделаны совершенно невнимательными. Вероятно по этой причине, для большинства людей, свойство быть невнимательным, кажется характерной особенностью машин. Например, если кто-то говорит, что некоторая задача "механическая", то это не значит, что люди не способны ее выполнить, это значит, что только механизм мог бы выполнять эту рутину много раз подряд без жалоб и чувства скуки.
Скачек из Системы
Такое обычно свойственно интеллекту – взять да и выпрыгнуть из задачи, которую он пытается решить, поискать решение снаружи, со стороны. И часто такой взгляд извне приносит результаты. Я сказал, что интеллект может выпрыгнуть за пределы решаемой задачи, но это не значит, что так бывает всегда. Однако малейшее побуждение к этому, как правило, оказывается мгновенно удовлетворено. Например, человека читающего книгу, может сморить сон. Тогда вместо того, чтобы упорно продолжать читать до конца, он, по всей видимости, отложит книгу и выключит свет. Тем самым он сделает шаг "из системы" и этот выход выглядит вполне естественно в нашем мире. Или, предположим, персона А смотрит телевизор, когда персона В входит в комнату и демонстрирует свое неудовольствие ситуацией. Персона А полагая, что правильно понимает суть претензий В, начинает в рамках существующей системе пытаться улучшить ситуацию: манипулируя кнопками каналов, искать лучшую программу. Но персона В может иметь более радикальную концепцию, которая лежит "за пределами системы", а именно – выключить телевизор вообще!
Иногда случается так, что какой-либо человек увидит контуры системы, влияющей на судьбы многих людей. Он видит систему, которую раньше даже никогда не признавалась как система. Тогда этот человек порой вынужден тратить свою жизнь, дабы убедить других в том, что система действительно существует, нужно только выйти из нее, что бы увидеть очевидное!
Как же научить компьютеры выпрыгивать из системы? Я приведу пример, который удивил некоторых наблюдателей. Недавно, на шахматном турнире в Канаде, одна шахматная программа (и это была наислабейшая из всех представленных там программ) продемонстрировала необычную манеру заканчивать игру задолго до финального хода. Программа не была очень хорошим шахматистом, но этот недостаток с лихвой окупался ее способностью своевременно определить, что игра находиться в безнадежной ситуации и поэтому пора сдаваться, не дожидаясь пока соперник исполнит длительный ритуал нанесения окончательного поражения. Программа проиграла все партии. Но она их все проиграла очень стильно! На многих местных экспертов по шахматам это произвело неизгладимое впечатление!
Таким образом, если вы определите "систему" как "совершать шаги в шахматной игре", ясно, что эта программа имела хорошую способность к выходу из системы. С другой стороны, если вы думаете о выходе из "системе" как о действии, "которое не было запрограммирован заранее", тогда, без сомнения, компьютер не имеет вообще никакой возможности выйти из системы.
Очень важно при изучении формальных систем отличить работу в пределах системы от заключения утверждений или наблюдений относительно самой системы. Я полагаю, что вы, начав решать MU-головоломку, как и большинство людей, работали в пределах системы, но потом в вас начало расти беспокойство и это беспокойство, в конце концов, достигло той точки, где вы прекратили дальнейшие попытки добиться результата. Вы вышли из системы, попробовали оценить уже сделанное вами, и задались вопросом - почему до сих пор так и не смогли получить MU? Возможно, вы нашли причину почему не смогли получит MU. При этом вы уже думали относительно всей системы в целом. Возможно, вы получили MIII, где-либо в процессе работы, и этот результат вы могли получить, только работая внутри системы. Я не стал бы утверждать, что эти два способа полностью несовместимы. Я уверен, что каждый человек способен до некоторой степени работать внутри системы и одновременно размышлять относительно того, что он делает. Фактически, при решении реальных проблем, почти невозможно провести границу между тем, что находиться "внутри системы" и "снаружи". Жизнь состоит из такого количества взаимных связей и хитросплетений, часто содержит столько противоречивых "систем", что может показаться слишком упрощенным думать о ней в таких терминах. Но часто оказывается очень важным сформулировать простые и ясные идеи, дабы потом использовать их как модели в размышлениях относительно более сложных сущностей. И именно поэтому я демонстрирую вам формальные системы, поэтому нам пора вернуться к обсуждению MU-головоломки.
M-способ, I-способ, U-способ
MU-головоломка была предложена таким образом, чтобы подтолкнуть вас к некоторым самостоятельным исследовании MIU-системы, то есть, заставить вас лично получить некоторое количество теорем. Но задача было преподнесена и так, что совсем не гарантировала вознаграждение за упорный труд тому, кто останется внутри системы. Тем самым провоцировалось некоторое колебание в выборе между двумя методами работы. Лучший способ разрешить эти колебания – иметь два листа бумаги. На одном листе вы работаете "в меру своих способностей как машина", тем самым, заполняя этот лист только цепочками символов из M, I и U. На втором листе вы работаете "в меру своих способностей как разумное существо" и здесь разрешается записывать все идеи приходящие вам в голову в процессе решения задачи. Например, вы могли бы делать записи на человеческом языке, или предпринять попытку рассуждений в обратную сторону, при этом вы можете использовать всевозможные сокращения и специальные символы (типа символа 'x'), сжатие нескольких шагов в один. Вы можете пробовать поменять правила системы, чтобы посмотреть к чему это приведет, и увидеть что меняется, а что осталось неизменным. Одна вещь, на которую вы могли бы обратить внимание это то, что числа 2 и 3 играют важную роль, так как от символов I можно избавиться только имея их тройками, а от символов U избавляются только двойками. В то же время удвоение длинны цепочек (не считая первого символа M) допускается только правилом II, поэтому на вашем втором листе вполне могли бы появиться некоторые соображения на этот счет...
В дальнейшем мы будем иногда возвращаться к этим двум способам обращения с формальной системой, поэтому мы назовем их Механическим способом (M-способом) и Интеллектуальным способом (I-способом). Чтобы завершить перечень способов, используя весь алфавита MIU-ситсемы, я так же упомяну заключительный способ - способ Отрицания или Не-способ (U-способ), который является Дзен-способом, так сказать, приближения к сути вещей. Но относительно этого способа мы узнаем в последующих главах.
Разрешающая процедура
Наблюдая за головоломкой, можно сказать следующее: все правила разделяются на две группы, каждая из которых имеет противоположную друг другу тенденцию - удлиняющие правила и сокращающие правила. Два правила (I и II) позволяют вам увеличивать длину цепочек (строго определенным способом, конечно), два других правила позволяют вам сокращать длину цепочек (опять же жестко предписанным способом). Кажется, имеется бесчисленное разнообразие возможностей, в которых эти различные правила можно было бы комбинировать, и это вселяет надежду, что так или иначе MU все же можно было бы получить. Так мы могли бы попробовать сначала получить цепочку гигантских размеров, а потом сокращать в ней фрагмент за фрагментом, пока не останется только те два вожделенных символа. Или (хотя это худший вариант) процесс мог бы состоять из серии удлинений, а потом ряда сокращений, потом опять удлинений и сокращений. И так далее. Но нет никакой гарантии, что это приведет к успеху. Фактически, мы уже имели возможность убедиться, что цепочка U не может быть получена вообще ни каким способом, и как бы вы ни старались, но в попытках удлинять и сокращать цепочки символов вы сможете дождаться не решения, а только конца света.
Однако случай U и случай MU кажутся во многом различными. Благодаря очень простому критерию мы легко признали получение U невозможным: строка не начинается с символа M (принимая во внимание, что все теоремы должны начинаться). Очень удобно иметь такой простой критерий проверки не принадлежность к множеству теорем. Однако, кто может гарантировать, что проверка первого символа позволяет обнаружить все не теоремы? Может, имеется большое количество цепочек, которые начинаются с M, но их никак нельзя получить в системе. Возможно MU -одна из них. Это означает, что "правило первого символа" имеет ограниченные возможности, с его помощью можно обнаружить только часть не теорем, но не заметить остальные. У нас зарождается надежда, что возможно, существует некоторый более сложный, способ, с помощью которого совершенно четко можно отличить те цепочки, что могут быть получены в нашей системе, от тех, которые здесь получены быть не могут. Но тут мы останавливаемся перед вопросом: "что мы подразумеваем под критерием?" Не совсем очевидна причина, почему этот вопрос имеет смысл или важен в нашем контексте. Но я приведу пример "критерия", который, так или иначе, нарушает дух наших рассуждений.
Вообразите джина, владеющего неограниченным временем и который получает удовольствие от того, что тратит все это время на вывод теорем MIU- системы, довольно методичным способом. Вот, например, возможный путь, которым джин мог бы заниматься любимым делом:
Шаг 1: Применить каждое применимое правило к аксиоме MI. Это породит две новых теоремы: MIU, MII.
Шаг 2: Примените каждое применимое правило к теоремам, произведенным на шаге 1. Это приведет к получению трех новых теорем: MIIU, MIUIU, MIIII.
Шаг 3: Примените каждое применимое правило ко всем теоремам, полученным на шаге 2. Это породит пять новых теорем: MIIIIU, MIIUIIU, MIUIUIU1U, MIIIIIIII, MUI.
*
*
*
Таким образом, джин породит каждую теорему системы рано или поздно, потому что правила применяются во всех мыслимых комбинациях. (См. рис. 11.) Все сочетания удлинений и сокращений, которые мы упоминали выше, в конечном счете, рано или поздно здесь встречаются.
РИС. 11. Показано систематическое построение "дерева" всех теорем MIU-СИСТЕМЫ. N-нный уровень внизу содержит те теоремы, происхождение которых требует точно N шагов. Числа в кружочках сообщают, какое правило использовалось на данной ветке дерева. Находится ли MU где-нибудь в этом дереве?
Однако, не совсем ясно как долго надо ждать появления вожделенной цепочки символов, ведь теоремы занесена в этот список в порядке длинны своего происхождения. Это не очень полезный порядок, если вы интересуетесь конкретной цепочкой (типа MU). И если вы не можете даже знать действительно ли эта цепочка когда-либо будет получена, то тем более не можете ведать, как много шагов для ее вывода потребуется!
Но теперь объясним предложенный ранее "способ" отличить теоремы от не теорем
Ждите, пока рассматриваемая вами цепочка не будет получена джином. Как только это случиться вы узнаете, что ваша цепочка - теорема. Если же этого никогда не случиться, значит, рассматриваемая вами цепочка - не теорема.
Такой подход выглядит абсурдным, потому как по нему предполагается, что мы не против ждать буквально целую вечность для получения необходимого ответа. Здесь мы подошли к сложнейшей сути того, что мы должны считать "критерием". Главнейший признак такого критерия - гарантия, что мы получим ожидаемый ответ за конечный промежуток времени. Поэтому если имеется критерий (способ) проверить любую цепочку на принадлежность к множеству теорем, который всегда заканчивается за конечный промежуток времени, то такой критерий (способ) называется разрешающей процедурой для данной формальной системы.
Если вы имеете разрешающую процедуру, тогда вы имеете очень конкретную характеристику всех теорем в системе. По неосторожности, нам могло бы показаться, что правила и аксиомы формальной системы обеспечивают не менее полную характеристику теорем, чем разрешающая процедура. Но вся хитрость в термине "характеристика". Конечно, и правила вывода, и аксиома MIU-ситемы неявно характеризуют те цепочки, которые являются теоремами. Даже более того, неявно они характеризуют те цепочки, которые теоремами не являются. Но неявной характеристики часто бывает недостаточно. Если кто-либо утверждает, что имеет характеристику всех теорем, но требуется бесконечно много времени для того, чтобы выяснить, что некоторые цепочки не теоремы, то вы, наверное, склонитесь к мысли, что в этой характеристике чего-то не так - она слишком расплывчата.
Именно поэтому обнаружить, что разрешающая процедура существует - очень важный шаг. Важно увидеть, что найденное средство, в действительности позволяет выполнить испытание на принадлежность любой цепочки к множеству теорем, и даже если это испытание очень сложное, то оно все равно гарантированно закончиться. В принципе такой критерий должен быть столь же легок, столь же механичен, столь же конечен и столь же убедителен, как проверка на наличие первым символом у всех теорем символа M. Разрешающая процедура - лакмусовая бумажка для всех теорем теории!
Кстати, одним из требований к формальной системе является то, чтобы множество аксиом характеризовалось разрешающей процедурой. Разрешающая процедура должна быть лакмусовой бумажкой на "аксиомность". Это гарантирует, что нет никаких проблем в самом начале, по крайней мере, в основании. В этом главное различие между множеством аксиом и множеством теорем: аксиомы всегда имеют разрешающую процедуру, но теоремы могут такой процедуры и не иметь.
Я уверен, что вы согласитесь со мной: когда впервые смотрели на MIU- систему, вы должны были видеть эту проблему отчетливо. Единственная аксиома была известна, правила вывода были просты, так что теоремы были неявно характеризованы. И тем не менее все еще было не ясно, является ли MU теоремой или нет?
Вопросы? Предложения? Претензии?
Обсудить материал в моем ЖЖ
|
[ назад ]
[ оглавление ]
[ вперед ]
A Semenov 2007
[ вверх ]
|
 |