Тьюринг и Гёдель — два взгляда на искусственный интеллект и не только
Привет! Меня зовут Саша Шутай, я руководитель направления PHP в AGIMA. Мы с командой подготовили большой разбор научных взглядов двух великих ученых: Алана Тьюринга и Курта Гёделя. Подумали, что будет интересно сравнить их биографии и подходы к искусственному интеллекту. Если тема зайдет, будем и дальше рассказывать об истории математики и разработки.
Как известно, у программиста стакан наполовину Алан, а у математика — наполовину Курт. Алан Тьюринг и Курт Гёдель — два величайших ума XX века, вклад которых в науку фундаментален. Полнота по Тьюрингу — критерий того, что вычислительная система способна решить любую разумную задачу. Неполнота по Гёделю — свойство любой достаточно сложной теории, из-за которого в ней нельзя ни доказать, ни опровергнуть некоторые утверждения.
Кажется, что из этих двоих Тьюринг — «хороший полицейский»: Тьюринг-полнота утверждает, что любая задача разрешима, даже если ты программист на Brainfuck. А Гёдель в этой парочке, соответственно, плохиш: его теорема говорит, что некоторые вещи не доказать совсем никак, и в свое время она конкретно обломала программу Гильберта по формализации всея математики. Все ли так однозначно? В чем на самом деле фундаментальное различие между их взглядами? Искусственный интеллект в заголовке — это кликбейт? Ответы на эти и другие вопросы ожидают вас под катом.
В биографиях Тьюринга и Гёделя можно найти много параллелей и противопоставлений. Они родились с разницей в шесть с небольшим лет, и оба были, как нынче говорят, вундеркиндами. Маленький Курт имел способность к языкам и еще до совершеннолетия выучил английский и французский. Кроме того, он с удовольствием изучал слово Божие и сохранил интерес к религии на протяжении всей жизни. Маленького Алана мало интересовали гуманитарные дисциплины, он с самого детства проявлял интерес к естественным наукам. Получив религиозное воспитание, Тьюринг тем не менее стал атеистом, когда трагически погиб его друг детства. Несмотря на все различия, вскоре Тьюринг и Гёдель нашли общую страсть — математику.
В любой статье по истории математики рядом с этими двумя именами обязательно будет третье, а именно — Давид Гильберт. Этот человек нашел много ответов, но гораздо важнее были поставленные им вопросы. Так называемые проблемы Гильберта — список из 23 вопросов, которые определили развитие математики на век вперед. Тьюринг и Гёдель хотели всего лишь решить некоторые из этих проблем, но в процессе сделали намного больше. Впрочем, об этом в следующем разделе.
Алан Тьюринг
Оба ученых слыли чудаками. У Тьюринга был старенький велосипед, с которого постоянно слетала цепь. Но вместо того, чтобы купить новый, Тьюринг рассчитал, через сколько оборотов колеса слетает цепь, и в нужный момент останавливался и поправлял ее. Гёдель же, эмигрируя в США, пытался доказать комиссии неполноту американской конституции, из-за которой возможно вполне демократическими методами установить диктатуру.
Истории обоих ученых кончились плохо. Тьюринг был осужден за нетрадиционную сексуальную ориентацию и прошел принудительную гормональную терапию, подорвавшую его здоровье. У Гёделя под конец жизни развилась паранойя, он панически боялся быть отравленным и в конце концов умер от истощения, отказавшись принимать пищу. По злой иронии, вместо него от отравления цианидом умер Тьюринг. Неизвестно, было это убийство или самоубийство.
Курт Гёдель
С возрастом Гёдель отошел от научных исследований, он занимался преподаванием и философией. Тьюринг до конца оставался активным ученым, но тоже размышлял над вопросами, которые можно считать философскими, — в частности, о возможности создания искусственного интеллекта. Так что — нет, ИИ в заголовке не кликбейт, но к этому мы вернемся позднее. Сейчас пора поговорить о том, что сделало этих двоих великими.
Главные достижения
Начало XX века — время пересмотра оснований математики. До того момента с математическими доказательствами обращались достаточно вольно, и это привело к такому количеству неясностей, противоречий и парадоксов, что было ясно — надо что-то менять. Математики того времени во главе с Гильбертом мечтали ввести единую строгую аксиоматику, подобную аксиомам Евклида в геометрии, и вывести всю математику из нее. А потом пришел Гёдель и все испортил.
В 1930 году Гёдель, молодой и на тот момент никому не известный ученый, явился на конгресс, посвященный основаниям математики, и обнародовал там свою теорему о неполноте. Она говорила о следующем: во всякой теории, достаточно сильной, чтобы включать в себя арифметику, будут утверждения, истинность или ложность которых невозможно доказать. Это разом ставило крест на мечтах Гильберта и компании. Какую аксиоматику ни введи, всегда найдется то, что в ней доказать нельзя. В частности, нельзя доказать непротиворечивость арифметики (о которой идет речь во второй проблеме Гильберта) средствами самой арифметики. Так Гёдель стал самым знаменитым обломщиком за всю историю математики.
Чтобы всем стало еще обиднее, доказательство было чудовищно простым (по меркам передовой математики) и напоминало диагональный метод Кантора. Гёдель использовал прием, позже названный в его честь гёделевской нумерацией. Он придумал способ, как пронумеровать все доказуемые утверждения теории, а затем показал, что всегда будет истинное утверждение, для которого номерка не хватает.
В дальнейшем Гёдель внес вклад в исследование континуум-гипотезы. Он показал, что в стандартной аксиоматике теории множеств невозможно доказать, что она неверна. Спустя 23 года Пол Коэн показал, что невозможно доказать и обратное. Таким образом, континуум-гипотеза стала наглядным примером неполноты теории множеств.
Теорема Гёделя о неполноте произвела впечатление на всех, и Тьюринг не был исключением. Но вместо того, чтобы стоять и благоговеть, он решил приспособить ее для нужд народного хозяйства. Использовав гёделевскую нумерацию, Тьюринг решил поставленную Гильбертом «проблему разрешения» — существует ли общий алгоритм проверки истинности утверждений. Оказалось, что такого алгоритма нет, но после теоремы о неполноте это уже никого особо не удивило и не расстроило. К тому же аналогичный результат годом раньше уже получил Алонзо Чёрч, научный руководитель Тьюринга. Так в чем же тогда цимес? В процессе работы над проблемой Тьюринг изобрел универсальный исполнитель алгоритмов, названный в честь него машиной Тьюринга. И это имело далеко идущие последствия.
Машина Тьюринга состоит из бесконечной ленты и головки чтения-записи. Лента разделена на клетки, в каждой из которых может быть записан некий символ. Головка умеет двигаться вдоль ленты, считывать символ в текущей клетке и перезаписывать его. Кроме того, головка может находиться в одном из нескольких состояний. А главное, для каждого состояния и для каждого текущего символа у нее есть инструкция, в какую сторону сдвинуться, какой символ записать и в какое новое состояние перейти. Звучит как очень примитивный язык программирования, и, в общем-то, так и есть. Но примитивный не значит ограниченный.
Вскоре выяснилось, что машина Тьюринга эквивалентна другим формальным исполнителям: машине Поста, нормальным алгоритмам Маркова и лямбда-исчислению Чёрча. Более того, согласно тезису Чёрча — Тьюринга, любой алгоритм, который поддается формальному описанию, может быть записан как программа для машины Тьюринга. А это значит, что на машине Тьюринга можно основывать всю теорию алгоритмов, а не придумывать ее заново для каждого нового компьютера. И наоборот, не обязательно строить новый компьютер для каждой новой задачи. Если компьютер способен эмулировать машину Тьюринга — он (потенциально) умеет решать любую разрешимую задачу. Это свойство называют Тьюринг-полнотой.
Важно понимать, что тезис Чёрча — Тьюринга — это не теорема, а эмпирическое утверждение. А еще необходимо помнить, что не все Тьюринг-полные вычислительные системы одинаково полезны — они могут различаться скоростью и асимптотикой. Ну и наконец, не каждая задача требует Тьюринг-полноты — регулярные выражения не полны по Тьюрингу, но для простого парсинга строк их вполне достаточно.
Позиция по поводу ИИ
Проблема разума, естественного и искусственного, волновала обоих ученых. Но подходили они к ней с разных концов.
У Гёделя был мистический склад ума. Он был математическим платонистом — верил, что математические объекты в самом деле существуют и человек не придумывает их, а открывает, воспринимая неким особым чувством. С помощью модальной логики Гёдель «доказал» существование Бога — точнее, формализовал доказательство Ансельма Кентерберийского. А отправной точкой всех его философских рассуждений было то, что вселенная обязана иметь смысл, — ведь отсутствие смысла приводит к абсурду.
Мистицизм Гёделя не влиял на математическую корректность его рассуждений, но придавал особое направление его исследованиям. Например, пообщавшись с Эйнштейном, он придумал так называемую вселенную Гёделя — корректное решение уравнений теории относительности, в котором возможны (и неизбежны) путешествия назад во времени.
Что касается проблемы разума, Гёдель считал, что человеческий разум невозможно свести к алгоритму. Он остроумно выводил это из собственной теоремы о неполноте. Если разум — это алгоритм, то для него должны существовать недоказуемые утверждения. Однако человек умеет доказывать недоказуемые утверждения, дополняя систему аксиом или изобретая новые способы вывода. Например, теорема Гудстейна недоказуема в арифметике Пеано, но успешно доказана в арифметике второго порядка. Следовательно, разум — не алгоритм, а человек — не машина.
Тьюринг, будучи материалистом, придерживался противоположной точки зрения. Мозг материален — следовательно, он является разновидностью машины, а значит, можно придумать эквивалентную ему машину Тьюринга. Это утверждение казалось Тьюрингу столь же очевидным, как Гёделю — наличие смысла у вселенной.
В 1950 году Тьюринг опубликовал свою знаменитую статью «Вычислительные машины и разум», предвосхитившую весь современный ML-хайп. Там он рассуждал о том, может ли машина сравниться с человеческим интеллектом и как понять, что это произошло. Для ответа на последний вопрос Тьюринг предложил «игру в имитацию», известную сегодня как тест Тьюринга. Машина достигла человеческого уровня интеллекта, если она способна выдать себя за человека.
Тьюринг рассмотрел девять основных возражений против возможности искусственного интеллекта и отверг их. Например, аргумент, что интеллект требует души, Тьюринг изящно парировал тем, что процесс создания ИИ можно считать процессом зачатия и «душа», что бы это ни значило, появляется в машине тем же путем, что и в оплодотворенной яйцеклетке. Аргумент Гёделя рассматривался как частный случай пятого возражения: «Можно создать машину, близкую к человеку по интеллекту, но она никогда не сможет сделать Х». Тьюринг не опроверг Гёделя напрямую, но высказал мысль, что подобные заявления происходят от недостатка воображения. Они основываются на том, каковы вычислительные машины сейчас, и не учитывают, как они могут измениться в будущем.
Тьюринг также рассуждал о том, как может быть устроен гипотетический искусственный интеллект. Он писал, что сначала нужно запрограммировать «разум ребенка» — машину, которая еще не умеет ничего полезного, зато умеет учиться. Затем «разум ребенка» нужно обучить — и получится полноценный искусственный интеллект. Что-то напоминает, не правда ли?
В итоге становится неясно, кто из этой парочки «хороший полицейский», а кто «плохой». Теорема Гёделя показывает ограничения математики —, но она же утверждает свободу человеческого разума. Машина Тьюринга всесильна —, но лишь в определенных рамках, и в эти же рамки загоняется людской интеллект. Что более оптимистично: возможность создать разумную машину или возможность быть умнее любой машины?
Ребенок Тьюринга и машина Гёделя
Современный ML в определенном смысле случаен. Нет математических гарантий, что учение действительно пойдет машине на пользу. Существует проблема переобучения, случаются непреднамеренные косяки в обучающих выборках и намеренное «отравление данных». Тьюринговский «разум ребенка» пытается учиться, но нужен хороший воспитатель, чтобы ребенок не научился плохому.
Исторически существовали и другие подходы к искусственному интеллекту — основанные на строгом доказательстве и формальном выводе. Машины такого типа начинали с аксиом и строили из них теоремы. Предполагалось, что рано или поздно машины доберутся до полезных теорем.
Малоизвестный факт: машина есть не только у Тьюринга. В 2003 году Юрген Шмидхубер предложил проект вычислительного устройства, которое он назвал машиной Гёделя. Ее фишка в том, чтобы полностью контролировать процесс обучения. Машина вносит изменения в свою программу, только если сможет сперва математически доказать, что эти изменения действительно максимизируют некую функцию полезности.
Машина Гёделя лишена недостатков современных нейросетей. Ее невозможно переобучить, запутать или обмануть. Но у нее есть другой недостаток: к сожалению, она не существует в сегодняшней реальности и не факт, что когда-то будет создана.
Интуитивно кажется, что строгие рассуждения и формальный вывод — это более перспективное направление развития ИИ, чем игры со статистикой. К сожалению, история рассудила иначе. Подход «закинуть в нейросетку побольше данных и посмотреть, что получится» наглядно демонстрирует свою эффективность прямо сейчас. Эта статья не была сгенерирована с помощью GPT (честное пионерское!), но такое уже почти-почти возможно. К тому же не исключено, что именно нестрогость и склонность к ошибкам даст возможность обойти теорему о неполноте. Может быть, гениальное прозрение — это ошибка мышления, которая неожиданно привела к успеху?
Сейчас, в 2024 году, кажется, что Тьюринг побеждает Гёделя по всем фронтам. Компьютеры, вычислительно эквивалентные машине Тьюринга, обучаются так, как предполагал Тьюринг, и уже проходят тест Тьюринга. Кроме того, каждое новое открытие в нейрофизиологии склоняет чашу весов в сторону точки зрения «человек = машина». Но не все так однозначно.
В истории ИИ было много циклов подъема и спада. За каждым прорывом следовали разочарование и стагнация, так называемая AI winter. Сегодняшняя «весна» — самая цветущая за всю историю искусственного интеллекта. И тем не менее нет оснований утверждать, что нынешний подход не упрется в какие-то фундаментальные ограничения и «весна» не сменится новой «зимой».
В январе этого года обнаружилось, что разрешимость некоторых вопросов машинного обучения зависит от истинности континуум-гипотезы — той самой, чью неопровержимость доказал Гёдель. Совпадение? Возможно.
Что касается природы человеческого разума, знаменитый физик Роджер Пенроуз выдвинул гипотезу, что работа мозга может быть основана на квантовых явлениях и потому не сводится к машине Тьюринга. В том, что касается философии, Пенроуз — идейный последователь Гёделя. Его теория сознания в научном сообществе считается маргинальной, но это еще не значит, что она неверна.
Сейчас вы читаете эту статью на устройстве, работающем по принципу машины Тьюринга. Но хотелось бы верить, что при этом мы с вами находимся во вселенной Гёделя. Не в той, где возможны путешествия назад во времени (хотя было бы прикольно), а в той, где есть смысл.
Если вам интересны статьи о математике и философии точных наук, дайте знать в комментариях. И заодно предлагайте темы — посмотрим, о чем можно еще написать. А если хотите почитать о чем-то более конкретном и прикладном — приходите ко мне в телегу. Там рассказываю про тимлидинг и управление разработкой.
