Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич

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

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

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

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

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

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

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

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

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