Бесконечные алгоритмы

 

 

Если наука может достичь своих целей, то и демон Максвелла тоже может достичь своих целей – пробить дыры в самом фундаментальном законе природы, открытом наукой.

 

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

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

из ночного мороза – бесплатно. Второй закон термодинамики будет нарушен, вечный двигатель станет возможным – и привычное научное видение мира окажется под угрозой.

 

Так что, скорее всего, у демона не получится «сжать» свои знания до нескольких простых формул и данных, которые рассказажут всю историю молекул в контейнере, где действует демон.

 

Но если демон не сможет этого сделать, это наверняка будет не по силам и человеку? Целью науки всегда было создание наиболее краткого из всех возможных описания мира. Но этой краткости, с которой может быть описан мир, есть свой предел. Иначе с демоном Максвелла будут проблемы.

 

Это следствие вопроса Войцеха Зурека: если мы сможем доказать, что у нас получится описать весь мир в достаточно краткой форме, самое фундаментальное утверждение в нашем восприятии мира будет сломано: нарушится второй закон термодинамики.

 

Демон Максвелла – это не просто проблема изучения тепла и термодинамики. Демон Максвелла – это проблема для всей нашей космографии –понятие о том, что весь мир может быть детально описан всего лишь несколькими короткими уравнениями почти божественной красоты, является неверным.

 

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

 

Это осознание, которое по понятным причинам было названо самым глубоким из всех когда-либо созданных доказательств, касается пределов уверенности человеческого знания, пределов того, что мы в состоянии доказать. Это доказательство того, что все доказать нам не удастся – даже если мы будем знать, что это правда.

 

Когда математик Курт Гедель опубликовал доказательство своей теоремы в январе 1931 года, он вряд ли осознавал, что это может соотноситься с термодинамикой и невозможностью построения вечного двигателя. Потребовалось еще полстолетия и стало возможным почти с облегчением осознать, что именно теорема Геделя привела к объяснению того, почему не работал демон Максвелла.

 

Ведь в теореме Геделя мы просто вплотную подходим к самому порогу всех формальных знаний – и, следовательно, в каком-то смысле к единственному точному знанию, которым мы в состоянии обладать: бесконечность истины никогда не получится охватить одной-единственной теорией.

 

Только сам мир настолько велик, чтобы понять весь мир. Невозможно создать такую карту всего мира, которая включала бы в себя абсолютно все, если только эта карта не будет являться самой территорией – а в этом случае она, конечно, не будет картой.

 

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

Современное представление математики о своих собственных основах было уничтожено одним ударом. Мечты об уверенности увяли.

 

«Wir Mussen Nur Wissen, Wir Werden Wissen». Это заключительная фраза, которую произнес великий математик Давид Гильберт в своей великой лекции, когда его родной город Кенигсберг сделал его почетным гражданином 9 сентября 1930 года. «Мы должны знать. Мы будем знать».

 

В течение десятилетий Давид Гильберт высказывался в пользу ясных и определенных логических основ математики. В 1900 он перечислил задачи, решение которых позволит взять основы математики под полный контроль. Необходимо было показать, что математическая наука включает в себя связную, непротиворечивую и исчерпывающую логическую систему.

 

Снова и снова в течение первых десятилетий 20 столетия Гильберт подчеркивал, что подобное абсолютное разъяснение основ математики не за горами и мысль о том, что любая математическая задача может быть решена, имеет под собой основания. «Мы все в этом убеждены!», - сказал он и продолжил описанием мечты математика: «В конце концов, когда мы посвящаем себя решению математической проблемы, нас привлекает именно зов, который мы слышим внутри себя: вот проблема, ищи решение, ты можешь найти его чистой силой своей мысли, так как в математике нет места понятию «ignorabimus» - «не знаем и не узнаем».

 

В 1930 году, когда Гильберту было 68 лет, он ушел с поста профессора в Готтингене, столицы немецкой математики, и одна из наград, которой он был удостоен, стала для него особенно ценой – он стал почетным гражданином своего родного города. Церемония проходила осенью, когда Немецкое общество немецких ученых и физиков собралось на свою 91-ю конвенцию в Кенигсберге, который играл очень важную и особую роль в интеллектуальной истории Германии – именно здесь жил и всю жизнь работал философ Иммануил Кант.

 

Давид Гильберт решил прочитать по этому случаю большую лекцию по случаю получения этого звания – лекцию, в которой он смог бы провести связь с Кантом, одним из самых великих философов современности – а, возможно, и самым великим. В работе под названием «Naturerkennen und Logik» он высказал прямую, хотя и вежливо сформулированную критику величайшего сына Кенигсберга.

 

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

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

С этим не согласился Гильберт. «Кант сильно переоценивал роль и размеры априори, - отмечал он по этому поводу. - Теория априори Канта содержит антропоморфический шлак, от которого нужно освободиться. После того, как мы от этого избавимся, останется только то априорное знание, которое является основой чистого математического знания».

 

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

 

В 1800-х годах французский философ Огюст Конт стал основоположником позитивизма – философской школы, которая говорит, что нам нужно ограничиться только знанием, которое имеет позитивное подкрепление – то есть может быть получено через опыт или путем логических, или математических доказательств. Все остальное ненаучно. Конт серьезно критиковал Канта.

 

Но по мнению Гильберта, позитивизм продвинулся не слишком далеко. Он выразил свое мнение по поводу Конта и его обсуждения проблемы нерешаемых задач (что является проблемой для любой философии, которая принимает только знание, правильность которого может быть доказана). Гильберт утверждал: «В попытках дать пример нерешаемой задачи философ Конт однажды сказал, что науке никогда не удастся установить секрет химического состава тел Вселенной. Через несколько лет эта проблема была решена… Истинная причина, почему, по моему мнению, Конт не мог найти нерешаемую задачу, состоит в том факте, что такой вещи, как нерешаемые задачи, не существует».

 

Нет предела познанию – все может быть понято, и однажды все будет понято. Мы должны знать. Мы будем знать.

 

В тот день Гильберт пришел на местную радиостанцию. Два кенигсбергских математика позаботились о том, чтобы свои заключения он мог повторить в студии, а его слова могли попасть в эфир и быть записаны для потомства.

 

Констанс Райд, которая написала хорошую биографию Гильберта, отмечает: «Его последние слова, произнесенные в микрофон, были твердыми и уверенными: «Мы должны знать. Мы будем знать». Когда он поднял глаза от бумаги и техник выключил запись, он засмеялся. Запись, которая была сделана по время последней части его речи в Кенигсберге, все еще существует. И в конце, если слушать очень внимательно, можно услышать, как Гильберт смеется».

 

Но Гильберт не знал, что в числе слушателей этого обращения был никому не известный 24-летний математик их Вены, который двумя днями ранее, 7 сентября 1930 года в первый

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

раз, скорее всего, без всякой задней мысли в том же самом Кенигсберге рассказал своим друзьям-математикам о сделанном им открытии – открытии, которое было основано на программе Гильберта об установлении основ математики. Но это открытие полностью разрушало эту программу.

 

Этим молодым человеком был Курт Гедель. Его упоминание об этом открытии прошло практически незамеченным среди его коллег. Он сделал его на семинаре по эпистемологии науки, который посещали многие великие математики тех дней. Однако важность этого открытия дошла до них только после того, как его теорема была опубликована.

 

17 ноября Гедель представил статью, в которой содержались сделанные им доказательства,

 

в журнал «Monatshefte fur Mathematik und Physik». Она была опубликована в январе 1931

 

года, но в рождественский сочельник 1930 года ассистент Геделя Пол Бернейс написал Геделю с просьбой предоставить ему копию для печати. Когда Бернейс рассказал Гильберту о работе Геделя, Гильберт «несколько рассердился». Но он высоко показал себя и как человек, и как ученый в 1939 году, вместе с Бернейсом расширив работу Геделя и добавив

 

в нее несколько важных технических деталей.

 

На могильном камне Гильберта в Геттингене высечены слова: «Мы должны знать. Мы будем знать». Но он прожил достаточно долго, чтобы понять: на самом деле нам это никогда не удастся.

 

В 1910-13 годах британский философ и математик Бертран Рассел и математик А.Н. Вайтхед опубликовали работу «Principia mathematica», которая была призвана вывести все математические теории из законов логики. Готовя эту работу, Рассел обнаружил то, что сегодня известно как «парадокс Рассела», который во всех отношениях испортил их общий проект. Выяснилось, что математике свойственны неотъемлемые противоречия: парадоксы появляются в системах, которые во всем остальном являются вполне логичными. Проблемы начались тогда, когда математические величины начали соотноситься сами с собой. Но Рассел считал, что с этой проблемой можно справиться. И очевидно, было найдено красивое техническое решение.

 

Статья Геделя, написанная в январе 1931 года, носила название «О формально неразрешимых утверждениях в «Principia mathematica» и сходных системах». Другими словами, свое осознание Гедель напрямую связывает с работами Рассела и Вайтхеда.

 

Бертран Рассел был человеком широких интеллектуальных способностей. Он стал одним из доминирующих философов 20 века, занимаясь почти всеми философскими дисциплинами (и в течение своей жизни принимая очень различные философские позиции). Когда он, как ему казалось, решил все фундаментальные задачи в «Principia mathematica», он оставил математическую логику.

 

В 1963 году он писал: «Прошло уже 50 лет с тех пор, как я серьезно работал над математической логикой, - и практически единственная работа, которую я с тех пор прочел

 

– это работа Геделя. Я, конечно, понял, что работа Геделя имеет фундаментальное значение

 

– но она меня озадачила. Она заставила меня порадоваться тому, что я больше не занимаюсь математической логикой».

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

Тем не менее именно благодаря работе Геделя тема столетия действительно начала разворачиваться.

 

«Я лгу». Это утверждение, парадокс лжеца, преследовало европейскую мысль на протяжении тысяч лет. Если оно истинно, то оно ошибочно – и наоборот. Лжец, который говорит, что он лжет, должен говорить правду: если он лжет, то, когда он говорит, что лжет, на самом деле не лжет.

 

Существует множество более техничных версии этого парадокса, но смысл у них один: при соотнесении с самим собой возникают сложности. Это касается случаев, когда человек утверждает, что он лжет, а также случаев, когда человек говорит очень кратко. Такие парадоксы отвратительны. Один из них известен как «антиномия Ричарда» и касается он теории множеств.

 

Гедель уничтожил надежду математической логики изучить утверждения, напоминающие подобные парадоксы – или антиномии, как их предпочитают называть философы. Одно из очень немногих нематематических предложений в его работе 1931 года гласит: «Аналогия этого аргумента с антиномией Ричарда бросается в глаза. Он также тесно связан и с «Лжецом».

 

Оригинальная идея Геделя заключалась в том, чтобы принять утверждение «Я не могу быть доказан». Если это верно, мы не можем это доказать. Если это неверно, то мы можем это доказать – то есть мы доказали правильность чего-то, что не является правильным. Утверждение может быть верным тогда и только тогда, когда оно не может быть доказано.

 

Для математической логики это было не очень хорошо – но не потому, что это было парадоксом, противоречием. Проблема скорее заключалась в том, что утверждение «Я не доказуем» верно. Оно значит, что существует истина, которую мы не можем доказать. Существуют истины, к которым мы не можем прийти путем математических или логических доказательств.

 

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

 

Это простая, но очень глубокая идея. И она ведет к пониманию того, что логическая система никогда не сможет доказать свою последовательность. Истина или правильность логической структуры или языка никогда не может быть доказана изнутри. Вам нужно находиться вне системы и сказать: «Она последовательна. Она цельная». Последовательность и свобода от противоречий никогда не могут быть доказаны изнутри системы.

 

Математик Эндрю Ходжес выразил это так: «Особое утверждение Геделя заключалось в том, что так как это невозможно доказать, то в определенном смысле это правда. Но чтобы сказать, что это «правда», необходим наблюдатель, который мог бы взглянуть на систему со стороны. Это невозможно показать, работая внутри аксиоматической системы».

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

Логика не может обойтись без человека.

 

«Люди часто воспринимают теорему Геделя как нечто негативное», - писал британский математик Роджер Пенроуз в 1988 году. Осознание Геделя обычно воспринимается как знак всего, чего не может сделать человек. Или, как об этом пишет датская философская литература, она воспринимается как аксиома бессилия. И на самом деле, доказательство Геделя является также и доказательством бессилия. Но не бессилия человека – а бессилия логики.

 

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

 

Но исторические обстоятельства сложились так, что открытие Геделя напоминало о заключениях предыдущей эпохи больше, чем знаменовало собой открытие новой.

 

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

 

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

 

Подобный крах позитивизма не вызвал удивления у Геделя, который посещал встречи в венском кругу: вся его математическая философия была вдохновлена Кантом, который подчёркивал, что мы не можем доказать все, что знаем, но должны принять: оно базируется на основаниях, которые не могут быть доказаны – априорных категориях.

 

Но Гедель был не просто оппонентом позитивизма. Он был платонистом. Его взгляды на математические числа были частично заимствованы от греческого философа, который вывел философию идей около 400 года до н.э. Идея Платона заключалась в том, что за воспринимаемой нами с помощью органов чувств реальностью лежит еще более реальная реальность, состоящая из фундаментальных принципов, идей, для которых реальность, которую мы воспринимаем, является не более чем подобием. Но эта реальность существует, осознаем мы это или нет.

 

Эта точка зрения существенно контрастировала с мнением большинства математиков в начале 20 века (но сегодня она получила гораздо более широкое распространение). Давид

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

Гильберт полагал, что математика является своеобразной игрой, которая доказывает свою правильность через формальную последовательность. Бертран Рассел воспринимал математику просто как один из видов прикладной логики. Другие, к примеру, датчанин Лютцен Брауэр, полагали, что математические величины представляли собой усовершенствованную человеческую практику – то есть нашу интуицию.

 

Но Гедель полагал, что реальность этих величин не имеет ничего общего с тем, можем ли мы доказать их последовательность или то, что они могут быть доказаны логически или применены на практике. Целые числа или другие математические величины существовали «там» задолго до того, как мы осознали их существование.

 

Эти взгляды Гедель сохранял с середины 20-х годов и на протяжении 30-х годов, когда он получал глубокие результаты в математической логике - один за другим. Он полагал, что эти взгляды являются жизненно важными для его научных достижений. Однако он их не обсуждал. Он не публиковал свои философские воззрения, даже несмотря на то, что философия являлась одним из главных интересов его жизни. Только в 1944 году его взгляды получили широкую огласку – в юбилейном сборнике статей в честь Бертрана Рассела. Математик и философ Соломон Феферман говорил о его статье так: «Гильберт умер в 1943 году, за год до того, как появился Гедель».

 

«В процессе подготовки вступительной главы по Геделю для предстоящего полного издания его работ я был поражен огромным контрастом, - писал Феферман, главный редактор Собрания работ Геделя, - между глубокими платоновскими убеждениями, которые Гедель сохранял относительно объективных основ математики и особой осторожностью, которую он проявлял в раскрытии этих убеждений».

 

Можно задать вопрос, чего стоило ему это молчание. Гедель не делился с людьми источником своих озарений. Он напрямую не раскрывал своих верований о мире. Он говорил другим только то, что мог доказать.

 

Гедель вел очень одинокую жизнь, доверял очень немногим людям и несколько раз лечился

 

в санаториях по поводу депрессии и переутомления. Он был сдержанным и подозрительным – не до такой степени, чтобы это обеспокоило докторов - несмотря на то, что был озабочен своим здоровьем. Его депрессия усугублялась и в 70-е годы превратилась

 

в паранойю с ее классическим синдромом страха отравления. В 1977 году ситуация стала критической – его жена попала в больницу и больше не могла за ним ухаживать. Он не открывал дверь медицинскому персоналу и 14 января 1978 умер. Его тело нашли в позе эмбриона. «Недоедание и истощение», которые стали результатом «нарушений психики» - такой была официальная причина смерти.

 

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

 

Сам Курт Гедель признавал следующую формулировку, которая пришла к нам от математического логика Хао Ванга: «В философии Геделю так и не удалось найти то, что

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

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

 

Безусловно, у Геделя тоже были подобные откровения. Но он не осмеливался их обсуждать. Он осмеливался открывать нам только те из них, которые мог однозначно толковать. Он осмеливался делиться своими откровениями только в том виде, какими они представали снаружи – с точки зрения всего остального общества.

 

Чудо математики состоит в том, что этого было достаточно, чтобы и другие могли увидеть свет.

 

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

 

Entscheidungsproblem.

 

Эта самая Entscheidungsproblem рассматривается по-другому: если у нас есть математическая система, которая говорит о частном предположении – можем ли мы решить, возможно ли вывести это предположение из системы? Гедель показал, что в любой закрытой системе возникнут вопросы, на которые не будет ответов – правдивые утверждения, которые не могут быть выведены. И это было критично, так как показывало, что мечта раз и навсегда уладить все в математике является недостижимой.

 

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

 

Но нет. Даже если этот вопрос может показаться скучным – ответ на него определенно таковым не является.

 

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

 

«Механический процесс». Алан Тьюринг принял во внимание выражение Ньюмана. Он подумал о машинах – машинах, которые могли бы считать. В 1935 подобные машины уже существовали – но они не представляли особого интереса. И Тьюринг начал рассматривать

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

принцип работы подобных машин: что нужно, чтобы машина могла решить математическую задачу и определить, может ли предположение быть получено из теоретической системы?

 

Требовалось не так уж много. Тьюринг изобрел простую логическую машину, которая не слишком много умела. Она могла выполнять несколько инструкций: писать, читать и выполнять в своей памяти исправления. Немногим больше, чем обычная печатная машинка.

 

Но Тьюринг оснастил свою логическую машину бесконечно большой памятью. Он предусмотрел для машины возможность записывать свою деятельность на рулоне бумаги бесконечно долго. Эта бумага могла перемещаться вперед и назад, так что машина – как и печатная машинка – работала на определенном участке в определенный момент времени. Этот бесконечный рулон бумаги – лента – был бесконечным вот почему: на самом деле неважно, насколько точно машина выполняла свои инструкции. Ведь у нее было достаточно памяти и достаточно времени.

 

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

 

Но вскоре Тьюринг понял и кое-что еще: алгоритм может быть написан так, что будет для машины «не пережевываемым» в понятной для нее манере. Были числа, к которым она не могла подобраться. И не потому, что числа были слишком большими – а потому, что алгоритм был слишком непостижим: невозможно было сказать, сможет ли машина справиться с числом, пока операция не была выполнена – а это могло занять бесконечно много времени. Таким образом никто не мог знать, удастся ли ему получить результат в течение конечного периода времени.

 

Это значит, что Entscheidungsproblem Гильберта была неразрешимой. Мы не можем создать алгоритм, который говорил бы нам, может ли что-либо быть выведено из математической системы.

 

Это заключение важно само по себе – и к нему одновременно и независимо пришел и другой ученый – американский логик Алонзо Черч.

 

Но в открытиях Тьюринга есть и еще одна интересная вещь: ему удалось сделать сразу два открытия одновременно, летним днем, лежа на лугу. В своей биографии Алана Тьюринга Эндрю Ходжес описывает это так:

 

«Алан доказал, что не существует никакой «чудесной машины», которая могла бы разрешать все математические задачи. Но в процессе он открыл кое-что столь же чудесное

 

– идею универсальной машины, которая могла бы взять на себя работу любой машины».

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

Тьюринг создал теорию машин, которые могли считать. Несколько лет спустя Вторая мировая война привела к тому, что значительные ресурсы были брошены на срочное развитие электронных компьютеров, особенно в Великобритании и США. Британцы пользовались ими, чтобы расшифровать секретные немецкие коды коммуникации. Американцы использовали их, помимо всего прочего, для создания атомной бомбы.

 

Со времен Второй мировой войны компьютеры стали обычным делом. Уже десятки лет человек увлечен идеей тех бесконечных возможностей, которыми наделили нас компьютеры и которые позволяют нам контролировать мир и следить абсолютно за всем.

 

Но факт заключается в том, что как только была изобретена концепция и теория вычислительных машин, Алан Тьюринг тут же осознал: мы не можем вычислить все. Человеческий разум оказался в состоянии сформулировать идею об универсальной вычислительной машине в тот самый момент, когда стало ясно: мы не в состоянии вычислить все механически. Существуют вопросы, возможность ответа на которые приходит только тогда, когда эти ответы получены – но не раньше.

 

Глубина этих отношений может оказаться для нас чуждой. Тезис Черча-Тьюринга просто утверждает, что мы можем вычислить все, что уже было вычислено. Вы можете делать все то, что, как вам известно, вы можете делать. А узнать, можете ли вы это сделать, вы сможете только после того, как уже сделаете!

 

Сегодня, когда компьютеры стали вездесущими, эта идея более знакома нам как «проблема остановки Тьюринга»: если говорить в целом, можем ли мы определить, когда компьютер закончит определенное вычисление? Ответом будет «нет»: мы не можем знать заранее, когда компьютер закончит вычисление (если, конечно, раньше он этого не делал).

 

Аналогично мы не можем знать, закончит ли компьютер вычисления вообще – до тех пор, пока он их не закончил. Пока он не закончил, мы не знаем, закончит ли он или будет продолжать работать вечно.

 

Это, конечно, не касается простых вычислений повседневной жизни – относительно них у нас есть большой опыт. Но мы знаем это только потому, что у нас уже есть подобный опыт. Нет принципиальных универсальных логических правил, которые могли бы сказать нам то, что было бы нам не известно.

 

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

 

В этом отношении компьютеры сходны с искателями истины и маленькими детьми. Все, что мы можем сделать – это ждать, пока они закричат: «Я закончил!».

 

«Большинство математиков, возможно, предпочли бы ограничить разглашение информации о текущем статусе математики «членами семьи», - писал в 1980 году Морис Клайн в своем предисловии к книге о том, как математика теряет уверенность. – Если об этих проблемах узнает общественность, это будет так же нехорошо, как распространять сведения о чьих-то проблемах в браке».

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

И действительно, в течение многих последних лет прошло несколько волн кризиса. Последовательность этих событий подытожил Руди Рукер в своей книге, опубликованной в 1987 году: «Теорема Геделя показывает, что человеческая мысль является более сложной и менее механической, нежели мы могли ранее полагать. Но после первоначального волнения 30-х годов результат свелся к небольшому количеству технической математики. Теорема Геделя стала частной собственностью представителей математической логики, и многие из этих академиков впадают в высокомерие при любом предположении о том, что эта теорема может иметь какое-то значение для реального мира».

 

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

 

Но теорема Геделя все же стала широко известной, и не в последнюю очередь потому, что в 1979 году американский ученый-компьютерщик Дуглас Хофстадтер опубликовал очень красивую, очень сложную и очень знаменитую книгу «Godel, Escher, Bach и Kомпания», в которой он указывает на духовное родство Иоганна Себастьяна Баха (1685-1750), чью музыку современники находили чересчур «математической», графического художника Мориса Эшера (1898-1972), до сих пор не вполне признанного коллегами, и Курта Геделя (1906-1978), информация о котором только сейчас распространяется в широких кругах.

 

Существовала и другая причина, почему мир начал замечать Геделя: стало ясно, что феномен, на который он указал, не был ограничен только странными парадоксами древних греков. Недоказуемость и неразрешимость являются фундаментальными характеристиками нашего мира.

 

Дальнейшее развитие теоремы Геделя в 60-е годы шло под различными названиями – теория алгоритмической информации, алгоритмическая степень интеграции, алгоритмическая случайность. Но какое бы название мы ни выбрали, отцов-основателей этого направления было три: Рэй Соломонофф, Андрей Холмогоров и Грегори Чаитин.

 

Сложно? На самом деле все не так сложно, как кажется. На самом деле с помощью этой теории можно гораздо проще выразить то, что открыли Гедель и его последователи. Она дает нам разумное определение того, чем на самом деле является случайность – а это важно, так как это дает нам намек на то, что такое порядок.

 

Отправной точкой здесь являются числа. Что такое случайное число? Так как все три эти джентльмена были математиками, у них была склонность к бинарным числам – то есть числам, которые состоят только из нулей и единиц: 010110100110 …

 

Такие числа сложно воспринимать визуально – но если перед ними поставить запятую, то они будут выглядеть как старые добрые десятичные дроби: 0.10110100110. Является ли это число случайным? На самом деле мы просто записали серию случайных двоичных цифр. Но была ли это просто случайность?

 

Мы могли с таким же успехом 12 раз бросить монетку, обозначив «орла» как 1 и «решку» как 0. В этом случае, конечно, число было бы случайным? Можем попробовать:

 

Перевод выполнен в ЦДС «Складчик» - Skladchik.com

 

100010000111 – нет, никакого обмана: мы бросили монетку 12 раз. Но если мы сделаем это еще раз, число, конечно, будет другим: 110011010000.

 

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

 

Вот это уже не кажется случайным – это последовательность 01. Такую последовательность можно было выразить проще: 0 точка 6 раз 01. Но на самом деле этот пример довольно хитрый, так как выразить данное число можно даже более кратко: это бинарное представление 1/3.

 

Смысл заключается в том, что определенные числа могут быть представлены в гораздо более краткой форме. К примеру, 111111111111111111 можно записать как «18 раз единица».

 

Если использовать десятичную систему, 0.42857142857 можно записать как 3/7, а 1234567891011121314151617181920 как «последовательность цифр от 1 до 20».

 

Но могут ли последовательности, которые мы получаем, бросая монетку, также быть записаны в краткой форме? Нет, не могут. Ведь они в