2.7.4 Теоретики - Гёдель, Чёрч, Тьюринг

Такой простой, на первый взгляд, вопрос требует для ответа на него весьма нетривиальных теоретических изысканий. Интересно, что вплоть до 1930-х гг., несмотря на, казалось бы, самоочевидность самого явления, у учёных не было формального определения для множества задач, которые могут быть решены при помощи бумажно-карандашных методов. Хотя для их обозначения имелся даже специальный, хотя и неформальный термин: «эффективно вычислимые задачи» (effectively calculable problems). В 1930-е гг. сразу несколько учёных попытались дать формальные определения этому понятию и подошли к проблеме, как часто водится, с разных сторон.

Из английской «Википедии» можно узнать, что в 1933 г. австро-американский математик Курт Гёдель вместе с Жаком Эрбраном дали формальное определение класса, подходящего в качестве аналога понятия «эффективно вычислимая задача». Этот класс был назван «общерекурсивными функциями» (general recursive functions). Класс общерекурсивных функций — это наименьший класс функций (с одним или более аргументом), он включает в себя все постоянные функции, проекцию, функцию следования и замкнутый относительно функций подстановки, примитивной рекурсии и минимизации.

У внимательного читателя после прочтения предыдущего абзаца наверняка возникнет как минимум два вопроса. Во-первых, что означает «австро-американский математик» — неужели на момент публикации статьи, содержавшей определение, у Гёделя было двойное гражданство? Во-вторых, что ещё более странно, как Жак Эрбран, умерший в 1931 г., смог в 1933 г. опубликовать вместе с Гёделем важный научный результат?

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

Жизнь Жака Эрбрана прервалась в 23 года в результате несчастного случая — молодой человек сорвался со скалы массива Экрен во Французских Альпах. Несмотря на возраст, Эрбран успел заслужить в глазах своих учителей звание «одного из величайших математиков нового поколения». Эссе Эрбрана «О непротиворечивости арифметики» (On the Consistency of Arithmetic), подписанное датой 14 июля 1931 г., было направлено автором для публикации в престижный немецкий «Журнал по чистой и прикладной математике» (Journal für die reine und angewandte Mathematik, часто его кратко называют «Журналом Крелле» по фамилии основателя) непосредственно перед отъездом на отдых в Альпы и получено журналом в день гибели математика, 27 июля. В процессе работы над эссе в начале 1931 г. Эрбран прочитал знаменитую статью Гёделя «О формально неразрешимых предложениях Principia Mathematica и родственных систем» (Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme), в которой Гёдель впервые сформулировал свои знаменитые теоремы о неполноте. По достоинству оценив результат, полученный Гёделем, Эрбран посвятил последний раздел своего эссе доказательству того, что положения его работы не противоречат выводам коллеги. В своём письме Гёделю, написанному в процессе работы над эссе, Эрбран сформулировал понятие рекурсивной функции, которое Гёдель впоследствии подверг обобщению, сославшись при этом на автора. Таким образом на свет появилось определение класса общерекурсивных функций.

Курт Гёдель родился 28 апреля 1906 г. в Австро-Венгрии, в городе Брюнне (сейчас — Брно в Чехии). В 1918 г., после распада империи, юноша получил чехословацкое гражданство, однако в 23 года официально перешёл в австрийское. Стоило Курту промедлить несколько лет, и тогда авторам «Википедии» пришлось бы, вероятно, писать уже о чехословацко-австрийско-американском математике.

В 18 лет, по стопам старшего брата, Гёдель отправляется в Вену, где поступает в университет, а в 23 года защищает диссертацию под руководством Ханса Хана, одного из основателей знаменитого «Венского кружка». В 1933 г. Гёдель становится приват-доцентом и в том же году впервые отправляется в США, для того чтобы принять участие в работе открытого в том же году Института перспективных исследований (Institute for Advanced Study, IAS) в Принстоне. В IAS Гёдель знакомится с американским математиком и логиком Алонзо Чёрчем и его учениками, а также с Альбертом Эйнштейном, который в будущем станет близким другом математика.

Рис. 43. Курт Гёдель и Альберт Эйнштейн

В 1934 г. Гёдель выступает в IAS с серией лекций «О неразрешимых теоремах формальных математических систем». Завершив курс в мае 1934 г., Гёдель возвращается в Вену. Его второй короткий визит в IAS продлился с октября по ноябрь 1935 г., но был прерван из-за приступа депрессии и выгорания. Возвращение домой не принесло покоя учёному. В июне 1936 г. Мориц Шлик, семинар которого пробудил в своё время у Гёделя интерес к логике, был убит одним из своих бывших учеников Иоганном Нельбеком. Убийство Шлика вызвало у Гёделя тяжёлый нервный кризис. У него появились параноидальные симптомы, в том числе страх быть отравленным, в результате чего математик провёл несколько месяцев в санатории для лечения нервных заболеваний. Современные исследователи расходятся во мнениях относительно мотивов убийства — не исключено, что дело было в банальной ревности. Тем не менее в своих собственных объяснениях убийца был весьма категоричен: он предъявлял Шлику обвинения в разложении культуры «христианского сословного государства» путём распространения неопозитивистских идей, говорил о вредоносности и «еврействе» произведений и лекций Шлика. Благодаря этим высказываниям Нельбек был помилован вскоре после того, как 12 марта 1938 г. Австрия в результате аншлюса стала частью фашистской Германии.

Немецкие власти отменили титул приват-доцента, поэтому Гёдель, в соответствии с новым порядком, должен был подать заявку на другую должность. Заявка была отклонена — против Гёделя сработали его былые связи с еврейскими членами «Венского кружка», особенно с Ханом.

20 сентября 1938 г. Гёдель женится на Адели Нимбурски, с которой он к тому времени был знаком более десяти лет. Семья не одобряла отношения Гёделя с разведённой танцовщицей, которая к тому же была старше его на шесть лет. В своих воспоминаниях брат Курта, Рудольф, писал: «Семья была недовольна его выбором. Конечно, она не была ему ровней в интеллектуальном плане, но это-то как раз было в порядке вещей. Она была выходцем из простонародья, чьи родители также жили на Лангегассе. Её отец был фотографом». Впрочем, наперекор всем предубеждениям в отношении детей фотографов сердечный союз между Куртом и Адель в итоге оказался очень крепким.

1 сентября 1939 г. началась Вторая мировая война. Положение Гёделя ещё более ухудшилось, поскольку немецкая армия нашла его пригодным для призыва на службу. Супруги решают покинуть Вену и бежать в США. Чтобы избежать затруднений при пересечении Атлантики, Курт и Адель добрались по Транссибирской магистрали до Тихого океана, на корабле пересекли океан, преодолев путь до Сан-Франциско, откуда на поезде отправились в Принстон, где Гёдель получил должность в IAS.

5 декабря 1947 г., когда Эйнштейн и Оскар Моргенштерн сопровождали Гёделя на экзамен на получение гражданства США, Гёдель признался им, что обнаружил формальный дефект в тексте Конституции, который мог позволить США стать диктатурой. Эйнштейн и Моргенштерн были обеспокоены тем, что непредсказуемое поведение их друга может поставить под угрозу результаты экзамена. Судьёй оказался Филипп Форман, который знал Эйнштейна и участвовал в слушаниях по его гражданству. Всё шло гладко, пока Форман не спросил Гёделя, думает ли он, что США могут прийти к диктатуре, подобной нацистскому режиму. Гёдель тут же начал объяснять своё открытие Форману. Форман понял, что происходит, прервал Гёделя и перешёл к следующему вопросу, после чего вынес рутинное положительное заключение. Эта точка стала последним поворотным пунктом в судьбе математика, окончательно связавшим его жизнь с США.

Позже в своей жизни Гёдель перенёс периоды психической нестабильности и болезни. Одержимый навязчивым страхом быть отравленным, он ел только ту еду, которую его жена готовила для него. В конце 1977 г. Адель была госпитализирована на шесть месяцев и больше не могла готовить для мужа. В её отсутствие он перестал есть и в конце концов умер от голода.

В ходе споров, развернувшихся между Чёрчем и Гёделем во время первого визита Гёделя в Принстон, произошло столкновение двух разных подходов к проблеме эффективной вычислимости. В отличие от Гёделя, который стремился создать способ описания всех возможных функциональных зависимостей, в том числе для функций, значения которых являются определёнными не для всех значений аргументов, Чёрч отталкивался не от функций, а от возможных способов вычисления. В итоге для формализации и анализа понятия вычислимости он создал «лямбда-исчисление» — систему, позволяющую при помощи минимальных средств выразить способ решения любой вычислимой задачи, имеющей символьное представление. После появления знаменитых теорем Гёделя о неполноте Чёрч первое время надеялся, что его лямбда-исчисление свободно от ограничений формальной арифметики, найденных Гёделем. Чёрч ошибочно полагал, что изъян формальной арифметики заключается в проблеме типизации, однако в конце 1933 — начале 1934 г. ученики Чёрча, Джон Россер и Стивен Клини, смогли показать, что лямбда-исчислению не удаётся избежать найденного Гёделем ограничения (Клини это открытие, кстати говоря, стоило переписывания почти готовой диссертации). Не растерявшись, Чёрч предложил использовать лямбда-исчисление в качестве способа определения эффективно вычислимых задач. Тезис Чёрча гласил: любая лямбда-определимая функция является эффективно вычислимой. Гёдель поначалу воспринял эту идею без особого энтузиазма, он считал, что эффективную вычислимость нужно сформулировать в виде набора общепризнанных аксиом. «Особая уличная магия» Чёрча не вызывала у Гёделя большого восторга.

Третий подход к вопросу об эффективной вычислимости был представлен в работах Алана Тьюринга.

Мы уже несколько раз упомянули Алана Тьюринга, и стоит сказать несколько слов о его биографии. Тьюринг происходил из древнего шотландского рода, имевшего, по всей видимости, французское происхождение. Его предки в течение нескольких поколений владели баронством Турин (Tourin) в Форфаршире (Forfarshire). Сэр Уильям Тьюрин был сподвижником короля Шотландии Давида II, разделив с ним изгнание. Впоследствии его лояльность была вознаграждена: ему было пожаловано баронство Фоверан (Foveran) в Абердиншире (Aberdeenshire), которым его потомки владели более 300 лет^, . С 1613 г. получило распространение новое (английское) написание фамилии — Тьюринг (Turing).

Родители Алана Тьюринга познакомились и поженились в Индии. Отец был служащим английского колониального ведомства, а мать — дочерью главного инженера Мадрасской железнодорожной компании. Алан был младшим ребёнком в семье (его брат Джон был на четыре года старше). В детстве Алан и Джон редко видели родителей — отец служил в Индии, где они с матерью проводили значительную часть времени вплоть до 1926 г., а дети оставались в Англии и жили на попечении в частных домах. В шесть лет Алан научился читать и увлёкся чтением научно-популярных книг. В одиннадцать он уже ставил химические опыты, впрочем проявляя мало интереса к другим предметам.

В 13 лет Алан поступил в престижную Шерборнскую школу (Sherborne Public School). Учебные успехи Тьюринга были крайне неровными. По меткому замечанию директора школы, Алан «…пытался построить крышу, не заложив фундамента». Провалы юноши чередовались с впечатляющими успехами. Он испытывал трудности в изучении языков и в то же время завоевал множество наград по математике. Но даже в ней он, увлекаясь сложными задачами, порой не уделял достаточно внимания основам. По всей видимости, его успехи напрямую зависели от интереса к изучаемому предмету. В письме матери Тьюринга директор школы Ноуэлл Смит дал Алану следующую характеристику: «Этот мальчик из тех, кто непременно станет некоторой проблемой для любой школы или сообщества, будучи в определённом смысле явно антисоциальным. Но я думаю, что в нашем сообществе у него есть хорошие шансы развить свои особые способности и в то же время немного научиться искусству жизни». Несмотря на трудности социализации, которые испытывал Алан, директор проявлял участие и терпение. Он считал, что этому мальчику (которого он в шутку прозвал «Алхимик») суждено сделать важный вклад в науку. Перед тем как директор Ноэулл Смит ушёл в 1927 г. в отставку, его жена (знавшая многих учеников) писала матери Тьюринга: «Мы будем с большим интересом следить за карьерой вашего мальчика. Я убеждена, что он сделает что-то великое в науке. Каждый раз, когда я встречала его, даже когда он помогал мне пропалывать сад, я чувствовала его силу. Полагаю, что он очень часто раздражает, я не знаю, что это такое… но подобное часто бывало с великими учёными, в детстве они были похожи на вашего мальчика».

И действительно, интересы мальчика позволяли предположить, что ему суждено стать учёным. Уже в 15 лет он самостоятельно освоил основы общей теории относительности и квантовой механики (хотя в ту пору эти теории ещё не были общепринятыми среди физиков). В 1928 г. в школе появился новый ученик — Кристофер Морком, который стал другом Алана. Кристофер разделял интерес Тьюринга к науке, и позже друзья решили вместе поступать в Кембридж. Однако с первой попытки сделать это удалось только Кристоферу — Алан сдал экзамен в Кембридж, но был квалифицирован только на exhibition (вид стипендии, который ниже, чем обычная scholarship), и родители решили, что ему стоит пока остаться в школе и попробовать поступить ещё раз через год. Однако 13 февраля 1930 г. Кристофер внезапно умер от осложнений «бычьего туберкулёза» — юноша заболел, выпив заражённого молока. Скоропостижная смерть друга потрясла семнадцатилетнего Тьюринга, и впоследствии он много рассуждал о проблеме человеческого существования.

Со второй попытки Алану всё же удаётся поступить в университет — в 1931 г. он становится студентом кембриджского Кингс-колледжа. Юноша продолжает интересоваться физикой — большое впечатление на Алана произвела книга фон Неймана «Математические основы квантовой механики» (Mathematische Grundlagen der Quantenmechanik). Читая её, Тьюринг не предполагал, что всего через несколько лет фон Нейман предложит ему место в Принстоне — одном из самых престижных университетов США, а ещё позже фон Нейман, так же как и Тьюринг, станет одним из признанных «отцов информатики». В университете Тьюринг занимается математикой под руководством известного учёного Макса Ньюмана. Позже, во время работы Тьюринга над взломом немецких шифров, уже Ньюман будет работать под руководством своего ученика. В свободное время Тьюринг проводит химические опыты, решает шахматные задачки, играет в го (игра интересовала его как модель для решения математических задач из теории групп), занимается спортом (греблей и бегом).

Тьюринг блестяще оканчивает четырёхлетний основной курс обучения. За свою работу в области теории вероятностей Алан получает специальную премию и звание King’s College Fellow, представлявшее собой нечто среднее между аспирантом и преподавателем. Именно в это время он начинает заниматься проблемами, которые позже привели его к созданию теории логических вычисляющих машин.

Тьюринг отталкивался от конструкции гипотетического устройства, способного решить любую «эффективно вычислимую задачу». Таким гипотетическим устройством стала машина Тьюринга (далее — МТ), впервые описанная в статье «О вычислимых числах, с приложением к проблеме разрешимости» (On the Computable Numbers, with an Application to the Entscheidungsproblem). Рассмотрим её конструкцию.

Первым элементом МТ является лента бесконечной длины, разделённая на ячейки. Каждая ячейка может хранить произвольный символ (на практике достаточно двух: 0 и 1). Кроме того, есть считывающая головка, способная обследовать одну ячейку ленты. После обследования лента может быть смещена на одну ячейку влево или вправо по отношению к головке. МТ руководствуется набором правил перехода. В каждый момент она находится в определённом состоянии, которому соответствует некоторое подмножество правил перехода. Каждое правило гласит: если машина находится в состоянии X с символом Y в ячейке ленты, пребывающей под считывающей головкой, то символ Y следует заменить новым символом Y′, переместить ленту на одну ячейку влево или вправо и изменить состояние на X′. Произвольное множество правил может быть само записано в виде последовательности символов на ленте МТ. Тьюринг использовал это свойство для определения понятия универсальной машины Тьюринга (УМТ), которая представляет собой МТ, способную имитировать произвольную МТ по её описанию на ленте. Такая способность УМТ напоминает способность молекулы ДНК кодировать саму себя.

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

Entscheidungsproblem в переводе с немецкого дословно означает «проблема (или задача) решения», по-русски мы обычно говорим «проблема разрешения». Впервые проблема была сформулирована в 1928 г. Давидом Гильбертом, едва ли не самым известным математиком XX столетия. Вопрос задачи звучит следующим образом: существует ли алгоритм, который, получив на вход утверждение, отвечает «да» или «нет» в зависимости от того, является ли данное утверждение «универсально справедливым»? В соответствии с теоремой Гёделя о полноте исчисления предикатов утверждение является «универсально справедливым» тогда и только тогда, когда оно может быть выведено из аксиом. Поэтому проблему разрешения можно рассматривать как вопрос о существовании алгоритма, позволяющего определить, можно ли, используя правила логики, вывести заданное утверждение из аксиом. В 1936 г. Чёрчу удалось доказать принципиальную невозможность создания такого алгоритма. В том же году, но несколько позже этот же результат независимо получил и Тьюринг, и именно этому посвящена его статья «О вычислимых числах…». Сегодня мы называем полученный результат теоремой Чёрча — Тьюринга.

Тьюринг доказал, что его «универсальная вычислительная машина» способна выполнять любые мыслимые математические вычисления, если они могут быть представлены в виде алгоритма. Для того чтобы показать неразрешимость проблемы разрешения, Тьюринг доказал, что проблема остановки (halting problem) для машин Тьюринга неразрешима: невозможно гарантированно за конечное количество шагов алгоритмически решить, остановится ли когда-нибудь произвольно взятая машина Тьюринга.

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

В 1939 г. Джону Россеру удалось доказать, что все три подхода — общерекурсивные функции Гёделя, универсальная машина Тьюринга и лямбда-исчисление Чёрча — являются взаимно эквивалентными и, следовательно, все три могут быть равнозначно использованы для определения эффективной вычислимости.

Интересными побочными продуктами изысканий Тьюринга стали понятия тьюринг-эквивалентности и тьюринг-полноты. Две машины P и Q являются тьюринг-эквивалентными, если машина P может симулировать работу машины Q и, наоборот, машина Q может симулировать работу машины P. Тьюринг-полной машиной называется машина, способная симулировать работу машины Тьюринга. Разумеется, не существует физических устройств, обладающих бесконечным объёмом памяти — аналогом бесконечной ленты МТ. Но это ограничение при использовании понятия тьюринг-полноты обычно игнорируется, то есть тьюринг-полными называют машины, которые при наличии у них бесконечной памяти могли бы выполнять любые вычисления, доступные МТ.

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

Так кому же принадлежит приоритет в создании такой машины? В своей работе, написанной в 1997 г., доктор Рауль Рохас показал, что машина Цузе Z3 может рассматриваться как тьюринг-полная. Для этого, однако, нужно совершить некоторый трюк, а именно склеить между собой два конца перфоленты, кодирующей программу. В машине Цузе не было операторов цикла или условного перехода, однако создание искусственного цикла, в который будет обёрнуто «тело» программы, позволяет тем не менее достичь желанной тьюринг-полноты. В принципе, подобный трюк мог бы быть возможен для Z1 и Z2, однако в случае Z1 машина не останавливалась при делении на ноль (единственной причиной остановки было достижение конца программы), что делало при закольцованной ленте остановку машины невозможной, следовательно, Z1 даже теоретически не могла стать тьюринг-полной машиной, а Z2, как указывает профессор Рохас, испытывала большие проблемы ввиду ненадёжности работы многочисленных реле и так и не стала полностью функциональной машиной.

По крайней мере до 1946 г. Harvard Mark I умел выполнять операции лишь строго последовательно, а без возможности осуществления условного перехода машина не может быть тьюринг-полной.

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

‎

Loading comments...