Источник: сообщество Тьюринга.

Автор: Линь Цзюнь Цен Фэн.

У Вэньцзюнь за работой (12 мая 1919 г. — 7 мая 2017 г.). Источник: Академия математики и системных наук Китайской академии наук.

1979 год был важным годом для Китая. В этом году произошло много важных событий, и он также считается важным поворотным моментом в политике, экономике, технологиях, культуре и других областях Китая, а также одним из важных переломных моментов в современной китайской истории. По сравнению с великолепной новой эрой, начавшейся в 1979 году, начало исследований в области искусственного интеллекта (ИИ) в Китае в 1979 году можно рассматривать только как незаметную волну в историческом приливе, но в истории искусственного интеллекта Китая это новаторское событие.

Самой ранней школой искусственного интеллекта была школа символизма.Большинство первых ученых, занимающихся искусственным интеллектом, были математиками и логиками.Они объединили компьютеры со своими собственными исследованиями после рождения компьютеров, таким образом войдя в область искусственного интеллекта. В Китае именно математики открыли первую страницу исследований искусственного интеллекта. В 1979 году, будь то «метод Ву» в машинных доказательствах, который пошел в мир, или проведение Летнего симпозиума по компьютерным наукам, сравнимого с Дартмутской конференцией, за этим стояли математики. Также с этого года искусственный интеллект Китая начал догонять мир.

Автором «метода Ву» является не кто иной, как математик Ву Вэньцзюнь. Вместе с Ван Сянхао и Цзэн Сяньчан его называют «тремя мастерами машинного доказательства». В конце 1970-х годов У Вэньцзюнь, которому было почти шестьдесят лет, начал с изучения древней китайской математики и создал новую область математической механизации.Он предложил «метод Ву» для доказательства геометрических теорем с помощью компьютеров, который считается новаторская работа в области автоматического мышления.

1. У Вэньцзюнь открыл дверь китайскому искусственному интеллекту в мир

В январе 1979 года по приглашению Института перспективных исследований в Принстоне математик У Вэньцзюнь сел на рейс по обмену в Соединенные Штаты с 25 000 долларов в кармане.

Его сопровождал математик Чен Цзинжунь. Эти двое являются первой группой ученых, приглашенных для обучения и посещения Соединенных Штатов после установления дипломатических отношений между Китаем и Соединенными Штатами.Они будут учиться и обмениваться в Институте перспективных исследований в Принстоне в течение определенного периода времени. Тема обмена Чэнь Цзинжуня, естественно, «1+2», и основное содержание обмена У Вэньцзюня в этой поездке, помимо его старой профессии топологии, больше касается истории древнекитайской математики и математической механизации. чтобы использовать 25 000 юаней, которые он принес Доллары, купить компьютер для изучения математической механизации.

Когда У Вэньцзюнь в 1979 г. получил первую премию в области естественных наук Китайской академии наук (далее именуемой «Китайская академия наук»), математическая механизация стала его основным направлением исследований. Это направление исследований также привлекло внимание всего мира.Метод исследования Ву Вэньцзюня называется «Метод Ву» в области доказательства машинных теорем.Высшая награда Китая в области интеллектуальной науки и техники «Премия Ву Вэньцзюня в области науки и техники в области искусственного интеллекта» использует Имя У Вэньцзюня в память о Ву Вэньцзюне как о достижениях китайских исследователей в областях, связанных с ИИ.

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

В 1970-е годы зарубежные академические обмены стали постепенно восстанавливаться. В 1975 году У Вэньцзюнь поехал во Францию по обмену и выступил с докладом о древнекитайской математической мысли во Французском институте передовых наук. В это время У Вэньцзюнь восстановил древнее доказательство формулы Ригао и заметил «структурные» и «механистические» характеристики древней китайской математики. На Весеннем фестивале 1977 года Ву Вэньцзюнь вручную проверил осуществимость метода машинного доказательства геометрической теоремы, и этот процесс длился два месяца.

Первоначальная идея машинного доказательства теорем исходит от рассуждения Готфрида Вильгельма Лейбница по исчислению, а позже развилась из символической логики. Позже Давид Гильберт (David Hilbert) запустил на этой основе в 1920 году «Гильбертовский проект», надеясь строго аксиоматизировать всю математическую систему. Проще говоря, если этот план реализуется, значит, по любой математической догадке, какой бы сложной она ни была, мы всегда можем узнать, верна ли она, и доказать или опровергнуть ее. Именно это имел в виду Гильберт, когда сказал: «Wir müssen wissen, wir werden wissen» (мы должны знать, мы должны знать).

Однако вскоре после этого, в 1931 году, Курт Гёдель предложил теорему Гёделя о неполноте, которая разрушила гильбертовские идеалы формализма. Но в любом случае, когда Гёдель закрыл дверь, он все же оставил окно. Докторская диссертация французского гениального математика Жака Эрбранда заложила основы теории доказательств и теории рекурсии математической логики.После того как была предложена теорема Гёделя о неполноте, Гербранд проверил свой тезис и ушел Одним словом - Гёдель и мои результаты не противоречат друг другу, а я написал письмо Гёделю за советом. Гёдель ответил Эрблану, но Эрблан не дождался письма: он погиб в результате несчастного случая во время альпинизма через два дня после того, как Гёдель ответил, в возрасте 23 лет. Позже высшая награда в области доказательства теорем также была названа в честь Эль Брауна, а Ву Вэньцзюнь получил четвертую премию Эль Брауна за выдающиеся достижения в области автоматического мышления в 1997 году.

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

В 1936 году Тьюринг в своей важной статье «О вычислимых числах с приложением к проблеме Entscheidungs» (* О вычислимых числах с приложением к проблеме Entscheidungs*) доказательства Гёделя 1931 года и ограничений вычислений. В результате обсуждение было переработано, и формальный язык Гёделя, основанный на общей арифметике, был заменен простой формой абстрактного устройства, которое теперь называется машиной Тьюринга, и было доказано, что все вычислимые процессы могут быть смоделированы машиной Тьюринга. Это также важная теоретическая основа для информатики и искусственного интеллекта. Самая ранняя школа искусственного интеллекта - школа символов также расширена на основе операций формальной логики.

Возвращаясь к У Вэньцзюню, он работал на Пекинском заводе радио № 1, который производил компьютеры в 1970-х годах, и в то время он начал связываться с компьютерами и машинным доказательством теорем. «Как в полной мере использовать возможности компьютера и применять их в своих математических исследованиях» стало тем, что интересует Ву Вэньцзюня. Позже У Вэньцзюнь начал изучать историю древнекитайской математики и обобщил геометрическую алгебраическую тенденцию и алгоритмическое мышление древнекитайской математики. Обнаружив различные способы мышления между древнекитайской математикой и западной математикой, он решил использовать другой метод для машинного доказательства геометрических теорем.

В то время У Вэньцзюнь прочитал много иностранных статей и полностью понял машинное доказательство. В то время самые передовые исследования в области машинного доказательства теорем были сделаны логиком-математиком Ван Хао, который во время учебы на факультете математики Юго-Западного ассоциированного университета учился у знаменитого философа и «первого человека в китайской философии» Цзинь. Юэлин, а затем поступил в Гарвардский университет в США.Известный философ и логик Уиллард фон Куинн (В. В. Куайн) изучил основанную Куайном систему формальных аксиом и получил докторскую степень. Уже в 1953 году Ван Хао начал думать о возможности доказательства математических теорем с помощью машин.

В 1958 году Ван Хао использовал программу логики высказываний на компьютере IBM 7041, чтобы доказать все теоремы логики первого порядка в «Принципах математики», а в следующем году завершил доказательство всех 200 теорем логики высказываний. Значение работы Ван Хаочжи заключается в объявлении о возможности использования компьютеров для доказательства теорем. Когда он вернулся в Китай в 1977 году, он принял участие в нескольких симпозиумах, затрагивающих долгосрочное развитие науки и техники моей страны, и прочитал 6 специальных лекций в Китайской академии наук, которые оказали значительное влияние на отечественные исследования в области машиностроения.

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

Во-вторых, от механизации древнекитайской математической мысли до «метода Ву»

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

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

Древняя китайская математика и западная современная математика — это две разные системы. У Вэньцзюнь восстановил «Чжоу Би Суань Цзин» в соответствии со знаниями и обычным мышлением и рассуждениями древних в то время без использования «современных инструментов», таких как тригонометрические функции, исчисление, факторизация и решения уравнений высокого порядка в современной математике. Методы доказательства «Ригао Тушо», «Даянцюишу» и «Цзэнчэнкайфаншу» в «Девяти главах Шушу». Он считает, что древняя китайская математика имеет свои особенности, методу Цинь Цзюшао свойственны особенности конструкции и механизации, а численное решение алгебраических уравнений высокого порядка можно получить с помощью небольшого калькулятора. В отсутствие в то время высокопроизводительного вычислительного оборудования У Вэньцзюнь смог в полной мере использовать древнекитайские математические идеи для проведения исследований по уменьшению размерности, что также заслуживает похвалы.

Первой теоремой, которую У Вэньцзюнь доказал в соответствии с этой идеей, была теорема Фейербаха, которая доказывала, что «девятиконечная окружность треугольника касается вписанной в него окружности и трех описанных окружностей». Это одна из самых красивых теорем планиметрии, которую можно увидеть в эстетике У Вэньцзюня. В то время не было компьютера, поэтому У Вэньцзюнь считал вручную. Одной из характеристик «метода Ву» является то, что будет сгенерировано большое количество многочленов. Самый большой многочлен, участвующий в процессе доказательства, состоит из сотен элементов. Это вычисление очень сложно, и любая ошибка на одном шаге приведет к тому, что последующие вычисления будут неудача. На Весеннем фестивале 1977 года Ву Вэньцзюнь впервые успешно проверил метод машинного доказательства геометрической теоремы вручную, а затем доказал теорему Симсона на Great Wall 203 производства Пекинского радиозавода № 1.

У Вэньцзюнь опубликовал соответствующую исследовательскую статью «Проблемы определения элементарной геометрии и механизированное доказательство» в «Китайской науке» в 1977 году и отправил статью Ван Хао. Ван Хао высоко оценил работу Ву Вэньцзюня и в ответ предложил Ву Вэньцзюню использовать существующий пакет алгебры и рассмотреть возможность реализации метода Ву с помощью компьютера. Ван Хао не осознавал разницы между компьютерами, которыми в то время пользовались ведущие ученые Китая и США: Great Wall 203 может использовать машинный язык, но системы команд разных компьютеров не универсальны, и это неосуществимо. использовать существующий пакет алгебры. Так, позже У Вэньцзюнь просто позаимствовал в Институте математики Китайской академии наук небольшой калькулятор в подарок от иностранца, посетившего Институт математики Китайской академии наук, преобразовал данное предложение в алгебраическую форму, а затем использовали метод Цинь Цзюшао для вычисления уравнения высшего порядка.

Исследование Ву Вэньцзюня по машинному доказательству геометрических теорем было решительно поддержано Гуань Чжаочжи. Гуань Чжаочжи учился во Франции, был одним из основателей французского отделения Китайской ассоциации ученых, объединил группу выдающихся патриотически настроенных интеллектуалов, одним из которых был У Вэньцзюнь. В то время у Института математики Китайской академии наук, где работал У Вэньцзюнь, были сложные отношения.Одна фракция считала, что делать машинные доказательства было «бунтарством», и надеялась, что он продолжит заниматься топологическими исследованиями; Гуань Чжаочжи, который перешел от топологии и функционального анализа к теории управления, особенно поддерживал и понимал его.Скажем, У Вэньцзюнь может делать все, что хочет. Позже, когда Гуань Чжаочжи в 1979 году основал Институт системоведения Китайской академии наук, У Вэньцзюнь последовал за Гуань Чжао в Институт системоведения Китайской академии наук (рис. 1-1).

Рисунок 1-1 Первоначальное офисное здание Института системных наук Китайской академии наук (ныне здание Жунке) в начале 1980-х годов (слева направо: Сюй Гожи, У Вэньцзюнь, индийский ученый Гуань Чжаочжи)

Для доказательства более сложных теорем нужны более совершенные машины. Академик Ван Дэчжао, в то время директор Института акустики Китайской академии наук, дал совет У Вэньцзюню. Он сказал У Вэньцзюню, когда и где появится Ли Чан, секретарь партийной группы и вице-президент Китайской академии наук, но У Вэньцзюнь действительно поймал его. Ли Чанг был очень непредубежденным.Когда он занимал пост президента Харбинского технологического института (далее именуемого «ХИТ») в 1950-х годах, он превратил ХИТ в первоклассный национальный университет. Среди шести ключевых национальных университетов, определенных в 1954 году, Харбинский технологический институт — единственный, расположенный не в Пекине. Ли Чанг также оказал большую поддержку работе Ву Вэньцзюня.Обмен У Вэньцзюнем иностранной валюты в размере 25 000 долларов США на покупку компьютера в Соединенных Штатах был специально одобрен Ли Чангом. С помощью этого компьютера были быстро доказаны многие теоремы.

1970-е были также золотым веком машинного доказательства теорем. В 1976 году два американских математика доказали теорему о четырех красках, используя высокоскоростной электронный компьютер с расчетным временем 1200 часов, и решили сложную задачу, которую математики не решали более 100 лет. Причина, по которой теорема о четырех красках может быть доказана, заключается в том, что неприводимые множества и неизбежные множества конечны.Проблема «раскраски карты» теоремы о четырех красках, кажется, имеет бесконечно много отображений, но на самом деле их можно отнести к более чем 2000 видов основных форм, а затем используйте вычислительную мощность компьютера для перебора и проверки их один за другим. Метафорически говоря, этот подход похож на сборку кубика Рубика — разобрать кубик на части и снова собрать — неэстетично, но эффективно. Мы сейчас говорим, что ОШП-3 «делает чудеса с большими усилиями», но на самом деле доказательство теоремы о четырех красках является родоначальником «чудес с большими усилиями».

Однако эта практика использования компьютерных вычислительных мощностей для доказательства теорем грубой силой не может быть распространена. Первый шаг в доказательстве теоремы, формализация теоремы, требует полной и строгой формулировки. По этому поводу есть небольшая история об одном математике. Астроном, физик и математик ехали поездом в Шотландию. Они увидели за окном паршивую овцу. Астроном начал вздыхать: "Почему в Шотландии все овцы черные?" Физик поправил: "Надо сказать, что некоторые овцы в Шотландии черные». Самое строгое выражение исходит от математиков: «В Шотландии существует по крайней мере один мир, и есть по крайней мере одна овца, и эта овца черная по крайней мере с одной стороны». сказал, что математические проблемы делятся на две категории: одна «это тоже нужно доказать?», а другая «это тоже можно доказать?». Из этого мы можем видеть, как трудно доказательству быть признанным другими математиками. Точно так же, чтобы формализовать теорему в интерактивном средстве доказательства теорем, необходимо заполнить все технические детали, чтобы завершить «автоматизацию» рассуждений и, наконец, заменить теорему осуществимой, но требующей больших вычислительных ресурсов идеей решения проблемы. . Другими словами, этот метод по-прежнему опирается на понимание теорем математиками и может дать только «одну теорию и одно доказательство», что можно рассматривать только как доказательство теорем с помощью компьютера.

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

Машинное доказательство теорем опирается на алгоритмы. На ранней стадии исследователи часто пытались найти супералгоритм для решения всех проблем, но У Вэньцзюнь применил древнекитайские математические идеи к области машинного доказательства геометрических теорем, добившись «одного типа, одного доказательства». С этим соглашался и Ван Хао, который считал, что его ранние работы имеют что-то общее с методом, использованным У Вэньцзюнем, то есть сначала найти относительно контролируемое подполе, а затем найти наиболее эффективный алгоритм по характеристикам этого поля. подполе. Когда У Вэньцзюнь посетил Соединенные Штаты в 1979 году, он также отправился в Рокфеллеровский университет, чтобы навестить Ван Хао.Его работа в области машинной теоремы была оценена по достоинству, что имело определенное отношение к настоятельной рекомендации Ван Хао.

«Метод Ву» действительно распространился, совершив первый прорыв в машинном доказательстве теорем в 1980-х годах благодаря Чжоу Сяньцину, иностранному студенту в Соединенных Штатах, который прослушал курс машинного доказательства теорем Ву Вэньцзюня. Чжоу Сяньцин изначально хотел получить ученую степень У Вэньцзюня в области машинного доказательства, но он думал, что дифференциальная геометрия была его слабостью, поэтому он боялся, что не сможет сдать экзамен, поэтому его наконец приняли в университет. наук и технологий Китая (далее именуемый «Университет науки и технологий Китая»), а затем перешел в Институт вычислительных технологий Китайской академии наук под именем Дай Пей. В связи с этим я проверил геометрическую доказательный курс.

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

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

В 1983 г. в Колорадо, США, проходила Национальная академическая конференция по доказательству теорем с помощью машин, на которой Чжоу Сяньцин выступил с докладом «Доказательство геометрических теорем с помощью метода Ву». Общая программа, разработанная Чжоу Сяньцином, может автоматически доказывать более 130 геометрических теорем, включая доказательства более сложных теорем, таких как теорема Моллера, теорема Симсона, теорема Фейербаха о девяти точках окружности и теорема Дезарга. Впоследствии сборник статей этой конференции был официально опубликован в 1984 г. как 29-й том серии «Современная математика» в США, и в него также были включены две связанные статьи, присланные У Вэньцзюнем.

В июне 1986 года лауреат премии Тьюринга Джон Хопкрофт (John Hopcroft) и другие организовали семинар по автоматическим геометрическим рассуждениям, и часть доклада о семинаре была включена в «Искусственный интеллект» специального выпуска «Интеллекта», вводной статьи в специальном выпуске специально представлен новый метод алгебраической геометрии, предложенный Ву Вэньцзюнем. Видение, твердотельное моделирование) также имеют важное прикладное значение (рис. 1-2). С тех пор Хопкрофт тесно сотрудничал со многими университетами Китая.У него есть возглавляемые им научно-исследовательские институты в Шанхайском университете Цзяо Тонг, Пекинском университете и Китайском университете Гонконга (Шэньчжэнь).У Вэньцзюнь и У Фафан, вероятно, положили начало его китайский комплекс.

Рис. 1-2. Обзор метода Ву во вступительной главе специального выпуска «Искусственный интеллект» 1988 г.