Тьюринг. Компьютерное исчисление

Глава 1 Что такое компьютер

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

Алан Мэтисон Тьюринг родился 2 июня 1912 года в Лондоне. За год до этого его родители, Юлиус Мэтисон Тьюринг и Этель Сара Стони, жили в индийском городе Чхатрапуре, отец работал в Индийской гражданской службе. Однако, ожидая появления на свет ребенка, Тьюринги решили, что это событие должно произойти в Соединенном Королевстве, поэтому переехали в Лондон, где и родился Алан, второй и последний их сын. После рождения Алана его отец подумал, что Индия — не самое лучшее место для новорожденного, так что Этель Сара и дети остались в Англии, а сам Юлиус отправился на службу в Чхатрапур. Семью он навещал время от времени. Когда Алану исполнился один год, его мать также уехала в Индию, чтобы жить вместе с отцом. Детей она оставила на попечении знакомых в Гилдфорде, и ближайшие несколько лет сыновья Тьюрингов видели родителей лишь изредка.

Тьюринги принадлежали к верхушке среднего класса, в котором чтили традиции и ценности британского образования. Сам Алан был от этих ценностей весьма далек, и это трагически повлияло на его судьбу. Ни по материнской, ни по отцовской линии в числе его родственников не было великих ученых и других знаменитостей. Единственным Тьюрингом, добившимся некоторой славы, был Харви Дория Тьюринг, дядя Алана, — он прекрасно ловил рыбу на муху. Однако, несмотря на отсутствие в семье интеллектуальной традиции, Алан еще в раннем возрасте начал демонстрировать высокие интеллектуальные способности. Рассказывают, что в детстве он очень интересовался числами, буквами и головоломками и на прогулках часто останавливался около фонарей, чтобы рассмотреть их серийные номера. В возрасте шести лет маленький Алан решил, что для сбора меда хорошо бы нарисовать маршрут, которым летают пчелы, и таким образом узнать точку пересечения их путей — именно в этом месте нужно ставить ульи. Также известна история о том, как он понял, что велосипедная цепь падает со звездочки через определенное количество оборотов — для этого мальчика гораздо интереснее было попробовать решить такую задачу, чем просто купить новую цепь.

Детское увлечение Алана Тьюринга наукой начало развиваться в школьные годы. В шесть лет мать записала его в государственную школу святого Михаила, в которой особая роль придавалась изучению латыни. Вообще встреча с английской образовательной системой имела для Алана как положительные, так и отрицательные последствия: с одной стороны, она стала для него источником знаний и сформировала его интеллект, с другой — Алан не мог не войти в конфликт с приверженностью этой системы непоколебимым классическим ценностям и опорой на Англиканскую церковь и британское величие. В атмосфере традиционной английской школы сформировалась такая характерная черта личности Алана, как уважение к нормам. В этом смысле показателен следующий эпизод: однажды мать читала Алану «Путешествие Пилигрима» (The piligrim’sprogress; 1678) — классическое сочинение английской литературы, написанное Джоном Баньяном (1628— 1688), — и пропустила часть текста, так как посчитала, что религиозное содержание отрывка может быть слишком скучным для ребенка. Однако Алан объяснил матери, что пропущенная часть — самая главная в книге и без нее вся история теряет смысл.

После окончания школы святого Михаила Алан пошел по тому же пути, что и его старший брат Джон. Сначала он поступил в центр Хейзелхёрст, а затем был записан в частную школу Мальборо. Как и многие его сверстники, Алан ставил элементарные химические опыты и увлекался популярной в то время книгой «Чудеса природы, о которых должен знать каждый ребенок»(Natural Wonders every child should know) Эдвина Тенни Брюстера (1866-1960). Благодаря этому сочинению юноша смог познакомиться с научным взглядом на природу.

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

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

которая по силам команде людей.

Алан Тьюринг, «Вычислительные машины и разум»

Алана привлекали математика, химия и, как ни странно, французский. Мать записала его в подготовительную школу Хейзелхёрст, где он делал успехи, но при этом не слишком выделялся — был обычным хорошим учеником. Но позже родителям пришлось забрать сына из Хейзелхёрста, по всей видимости из-за конфликтов с другими учениками. Тьюринг уже в те годы славился атлетическим телосложением, которое поддерживал в течение всей жизни. В Англии того периода атлетические данные были не менее важны, чем академические успехи, и все это, принимая во внимание интеллектуальное развитие мальчика, делало его априори хорошим учеником. И все же мать сомневалась в способности Алана соответствовать суровым требованиям престижной частной школы, а для нее было так важно, чтобы сына туда приняли, ведь это входило в число обязательных признаков социального класса, к которому принадлежала семья Тьюрингов. В 1926 году, несмотря на все страхи матери, Алан успешно сдал вступительный экзамен в частную школу (Common Entrance Examination) и был принят в школу Шерборна.

Год обучения в ней решительным образом повлиял на формирование личности Тьюринга. Там проявился его интерес к разрешению задач, которые он сам перед собой ставил, и эти задачи далеко не всегда были связаны с темами, о которых рассказывали преподаватели. Как это часто происходит и сегодня, школьная система той эпохи не слишком поощряла одаренных учеников. Алан выигрывал школьные конкурсы по математике, изучил теорию относительности Эйнштейна, благодаря известной книге Артура Эддингтона «Природа физического мира» ( The nature of the physical world) познакомился с квантовой механикой. Тьюринг настолько выделялся среди остальных, что однажды директор школы сказал о нем:

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

Среди связанных с Аланом необычных историй, доказывающих его упорство и целеустремленность, часто вспоминают случай, произошедший, когда Тьюрингу было 14 лет. В 1926 году в Соединенном Королевстве была объявлена всеобщая забастовка, и Алану, чтобы попасть на занятия, пришлось проехать 100 километров на велосипеде из дома в Саутгемптоне до школы с ночевкой в пансионе.

В Шерборне Тьюринг учился с 1926 по 1931 год. По всей вероятности, жесткие требования и правила школы стали причиной его стеснительности и замкнутости. На занятиях по греческому, латыни и английскому Алан не блистал, а вот на уроках по математике его талант полностью раскрылся. Он смог получить бесконечную последовательность тригонометрической функции, в частности обратной функции тангенса:

arctgx = х - x³/3 + x⁵/5 - x⁷/7...

В 1928 году, в возрасте 16 лет, Алан смог понять труды по теории относительности Эйштейна, а в 1929-м он с большим интересом читал работы Шрёдингера по квантовой механике. Именно в это время он подружился с Кристофером Моркомом, который учился классом старше. Через два года этот крайне одаренный мальчик неожиданно умер от туберкулеза, но в течение этого короткого срока Кристофер и Алан стали лучшими друзьями и много говорили о науке. Впервые Тьюринг встретил сверстника, разделявшего его интересы. Благодаря этой дружбе изменились и личные качества Алана, который стал гораздо общительнее. Друзья вместе отправились в Тринити-колледж, в Кембридж, чтобы просить о двух стипендиях, которые позволили бы им учиться в этом престижном заведении. И здесь мы вновь сталкиваемся с упорством Алана, которому для получения стипендии Кембриджского университета пришлось сдавать экзамены дважды: вначале, неудачно, в 1929 году и во второй раз в 1930-м. Однако со смертью Кристофера все его юношеские мечты о дружбе, все общие надежды рухнули. Это событие очень повлияло на Алана, который погрузился в глубокий душевный кризис и разочаровался в религии. Любопытно, что в течение практически трех лет (это видно из писем Тьюринга к матери Моркома) он был занят вопросом, как человеческий разум, в том числе и разум его друга, помещается в материи, то есть человеческом теле. Несмотря на зарождающийся атеизм Алан уверовал в бессмертие разума и заинтересовался, как именно происходит его отделение от тела после смерти. Прочитав труд Эддингтона, он предположил, что этот вопрос может быть связан с квантовой механикой. Учитывая возраст Тьюринга на тот момент, это доказывает его дарование и талант, ведь данная гипотеза, а именно роль квантовой механики в проблеме отношения разума и материи, лежала в основе исследований многих ученых середины XX века.

Наука — это дифференциальное уравнение.

Религия — граничные условия.

Алан Тьюринг в письме английскому математику Робину Гэнди

В 1931 году Алан Тьюринг стал студентом математики Королевского колледжа Кембриджского университета. С этих пор он отдалился от старшего брата Джона, который занялся адвокатской практикой в Лондоне. К счастью для Алана, университет был для него более подходящим местом, чем школы, в которых он успел поучиться: в Кембридже он попал в интеллектуальную среду, необходимую для развития его способностей. Свободное время Тьюринг посвящал занятиям спортом — бегу и гребле. Что касается его академических интересов, то после прочтения работы Джона фон Неймана о логических основах квантовой механики внимание Алана привлекла математическая логика. Известно, что он также прочел книгу Бертрана Рассела (1872-1970) «Введение в философию математики» (Introduction to mathematical philosophy, 1919) и знаменитый трехтомник «Принципы математики» (Principia mathematical 1910-1913), написанный Расселом совместно с Альфредом Нортом Уайтхедом (1861-1947). Без сомнения, эти работы повлияли на интеллектуальное созревание личности будущего ученого.

Алан Тьюринг в 1928 году в возрасте 16 лет.

Здесь родился Алан Тьюринг, 1912-1954, криптограф, пионер информатики. Надпись на одной из пяти синих табличек, размещенных на разных зданиях Соединенного Королевства, где жил Тьюринг.

Королевский колледж Кембриджского университета.

Однако наибольшее влияние на Тьюринга оказал Курт Гёдель (1906-1978), особенно его знаменитая статья, опубликованная в 1931 году и посвященная теоремам о неполноте. Эта работа подтолкнула молодого человека к изобретению машины Тьюринга, которая могла определять, какие математические функции могут быть вычислены, а какие нет. Если функцию возможно вычислить, машина через определенный промежуток времени, который, по словам другого великого математика, Давида Гильберта (1863-1943), должен быть конечным, выдаст результат. Напротив, если функция невычислима, машина будет производить операции без остановки. По мнению Ходжеса, Тьюринг был более философом, чем математиком, что и объясняет его интерес к проблемам математической логики. Ученый, возможно, сам не осознавая этого, внес большой вклад в создание теоретических основ информатики, причем сделал это задолго до того момента, когда компьютер стал реальностью.

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

В 1934 году Тьюринг закончил обучение в университете, получив диплом математика. В следующем году ему предоставили двухгодичную стипендию Королевского колледжа, входящего в Кембриджский университет. В этот период можно наблюдать первые вспышки его гениальности. В 1936 году Тьюринг получил премию Смита (в Кембридже ее присуждают молодым исследователям по теоретической физике, математике или прикладной математике) за работу по теории вероятностей под названием «О функции ошибок Гаусса» (On the Gaussian error function) — она не была опубликована. Любопытно, что в этом исследовании была заново открыта знаменитая центральная предельная теорема, одна из основных теорем статистики. В том же году Тьюринг написал научную статью, озаглавленную «О вычислимых числах, с приложением к проблеме разрешимости» (On computable numbers with an application to the Entscheidungsproblem), в которой описано его важнейшее научное достижение — машина Тьюринга. Эти труды обеспечили академическое будущее ученого и стали его первыми шагами к блестящей карьере.

Весной 1935 года Тьюринг посещал в кампусе Кембриджского университета, стипендиатом которого он был, курс Макса Ньюмана (1897-1984), знаменитого тополога, и у них завязалась долгая дружба. Топология — раздел математики, изучающий свойства объектов, которые остаются неизменными при непрерывных трансформациях. Тьюринг общался с Ньюманом в течение всей своей жизни, и это было чрезвычайно полезным для обоих с научной точки зрения. Во время Второй мировой войны они вместе работали в Блетчли-парке над расшифровкой перехваченных немецких сообщений, а позже в Манчестерском университете создавали программы для Baby, одного из первых послевоенных компьютеров.

В Кембридже Тьюринг смог принять участие в одном из самых интригующих этапов развития науки. Британский философ и математик Бертран Рассел утверждал, что логика является основополагающей при установлении математической истины. Эта идея была ключевой в его книге Principia mathematica, написанной незадолго до этого совместно с философом Уайтхедом. Если математика могла быть интерпретирована с точки зрения логики, в таком случае ничто не препятствовало ее сведению к основам логики. Одновременно, в начале 1930-х годов, другой философ и математик, Курт Гедель, уроженец Брно (этот город сегодня входит в состав Чехии, а в то время был частью Австро-Венгерской империи), установил в математике знаменитый философский принцип. Он ввел теорему о неполноте, которую можно представить как идею о том, что существуют неразрешимые математические выражения, или утверждения, которые не могут быть ни доказаны, ни опровергнуты. В общем случае эти утверждения могут быть истинными или ложными. Например, если кто-нибудь скажет, что «2 + 3 = 5», мы заметим, что это утверждение истинно. На математическом языке мы бы выразили это так:

А = [2+3=5] => [А истинно]

С другой стороны, если кто-то предложит утверждение «2∙3 = 8», мы скажем, что это утверждение ложно:

В = [2∙3=8]=> [В ложно]

Однако существуют утверждения, при установлении истинности или ложности которых мы сталкиваемся с парадоксом: утверждение начинает противоречить самому себе. Например, великий философ Сократ, говоря: «Я знаю, что ничего не знаю», противоречил сам себе, так как если Сократ знает, что «ничего не знает», значит, он «уже что-то знает». Классический пример, переводящий ситуацию из математической области в лингвистическую, называется парадоксом лжеца.

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

Представьте, что мы выражаем на математическом языке следующее утверждение G:

G = [это утверждение не истинно].

Если мы установим, что утверждение G истинно, мы подтвердим, что оно ложно. И наоборот, если мы решим, что G ложно, это будет означать, что G истинно. Этот парадокс имеет место в самореферентных системах, к которым принадлежит и фраза в описанном примере, и такой ее вариант, как «Я лгу». В результате мы получаем странную петлю. Независимо от того, как мы будем рассуждать, мы всегда приходим в ту же точку, откуда начали. Другими примерами самореферентности являются рука, рисующая руку, на знаменитой картине Эшера, синтез белков и ДНК клетки или «микрофон, слушающий колонку», представленный в книге Дугласа Хофштадтера «Я странная петля»(I am a strange loop).

«Рисующие руки» (1948), Мауриц Корнелис Эшер.

В тот период некоторые ученые сформулировали следующий вопрос: может ли математическая интуиция быть кодифицирована в свод правил, или (па современном языке) в компьютерную программу? Необходимо было понять, возможно ли создание механического разума, сегодня именуемого компьютером, с помощью которого мы сможем автоматически исследовать или доказать без вмешательства человека истинность или ложность какого-либо математического доказательства или утверждения. Например, для того, что мы сегодня называем искусственнглм интеллектом, не существует системы правил для вычисления или вывода, которая позволила бы определить с помощью программы свойства натуральных чисел. Натуральные числа N = [1, 2, 3, 4, ...], которые мы используем для счета элементов целой величины, например количества яблок, имеют определенные свойства.

Пусть a, b и с будут числом яблок, равным 2, 3 и 5 соответственно. Свойство ассоциативности устанавливает, что (а + 6) + с = а + (b + с), в то время как согласно свойству дистрибутивности а • (b + с) = а • b + а • с. Если мы представим эти два свойства натуральных чисел в виде утверждений, назвав ассоциативность утверждением H, а дистрибутивность — утверждением /, и заменим а, b и с их числовыми выражениями

Н = [(2 + 3) + 5 = 2 +(3 + 5)] => [Н является...],

I = [2 • (3 + 5) = 2 *3 + 2 • 5] => [I является...],

станет очевидно, что не существует программы для компьютера или какой-либо другой машины, которая могла бы автоматически доказать или опровергнуть этот тип утверждений. Как это ни удивительно, но написать программу для компьютера, которая доказала бы то, что очевидно даже ребенку школьного возраста, а именно (2 + 3) + 5 = 2 + (3 + 5), невозможно, поэтому в математике существуют «истинные утверждения» о числах, которые не могут быть доказаны с помощью правил дедукции. Как можно себе представить, теорема Геделя заставила пошатнуться казавшиеся непоколебимыми идеи Бертрана Рассела и сами столпы формальной математической науки, которыми так гордятся ученые.

Один из самых влиятельных математиков XIX — начала XX века, немец Давид Гильберт сказал, что вся эта дискуссия сводится к проблеме определения, то есть возможности установить последовательность или непоследовательность формальной системы. Это означает, что до сих пор математики делали свою науку, используя правила вывода и аксиомы, то есть идеи или утверждения, считающиеся очевидными и не требующие доказательств. В этой ситуации Гильберт поставил перед научным сообществом задачу создать механический процесс (на современном языке — «информатизированный процесс»), с помощью которого можно было бы принять решение об истинности или ложности математического утверждения. Необходимо было оставить теоретическую дискуссию, начатую Геделем, и найти реальное решение проблемы, так как на кону стояла честь математики как науки. Алан Тьюринг принял этот вызов и начал работать над решением проблемы, поставленной Гильбертом и ставшей, в свою очередь, ответом на теорему Геделя. Так Тьюринг создал абстрактный исполнитель, не имеющий реального прототипа, — а-машину (automatic machine). Это устройство, известное нам как машина Тьюринга, обязано своим происхождением дискуссии между философами и математиками на самом высоком уровне. Сегодня считается, что это теоретическая модель первого в истории науки компьютера. Однако, несмотря на гениальность идей, возникших у Тьюринга в 1937 году, они не могли получить материального воплощения. К сожалению, потребовался глобальный военный конфликт (Вторая мировая война) для того, чтобы математики и инженеры объединили свои усилия для разработки и создания удивительной машины — компьютера.

Итак, что представляет собой машина Тьюринга? Из каких частей или компонентов она состоит? А-машина — это абстрактное устройство, не имеющее реального прототипа и представляющее собой простейший компьютер. Она способна считывать и записывать символы на ленте, разделенной на ячейки. Теоретически эта лента бесконечна, то есть не имеет края ни справа, ни слева. Очевидно, что она представляет собой основную память; в современном компьютере эквивалентом можно считать оперативную память — RAM (ОЗУ, оперативное запоминающее устройство). Интересно отметить, что Тьюринг посчитал бесконечную ленту необходимой для компьютера, предваряя этим возникновение одного из важнейших элементов — памяти. По очевидным причинам память компьютера не может быть бесконечной, и этим объясняется «зависание» техники, когда ее памяти недостаточно для выполнения определенной программы или операции.

Но что можно записать на ленту? Представим, что мы располагаем алфавитом, состоящим всего из двух символов — 0 и 1, а также еще одним символом, означающим пустую ячейку, — назовем его пропуск, или В. Система из этих трех символов составляет алфавит, который мы обозначим как А. То есть в каждой ячейке бесконечной ленты будет записан символ: 0, 1 или В (см. рисунок).

Представим себе машину Тьюринга в самой элементарной конфигурации. С одной стороны, ей необходима головка для считывания и записи, с помощью которой считывается содержимое ячейки, а затем стирается и записывается новый символ. В общей модели машины Тьюринга считалось, что после завершения цикла чтения ячейки, стирания содержимого и записи нового символа головка и вместе с ней вся машина сдвигается по отношению к ленте на одну позицию вправо (П) или влево (Л). То есть можно представить, что лента или машина переходит к позиции П или Л. Также машине необходим небольшой объем памяти — реестр, в котором хранится информация о состоянии или конфигурации в определенный момент времени. Реестр похож на светофор, который может быть красным (К), желтым (Ж) или зеленым (3). В конкретный момент времени машина находится в определенном состоянии, и количество возможных состояний является конечным. Обозначим его множество буквой Q (см. рисунок). Представим, что наша машина находится в одном из четырех состояний: E1, Е2, ЕЗ или Е4. Также имеется начальное состояние 1₀, соответствующее записи в реестре при запуске машины в работу.

Итак, машина располагает двумя конечными наборами символов — величинами, записываемыми в ячейки ленты (А = (0, 1, В)), и состояниями реестра машины (Q = (I₀, El, Е2, ЕЗ, Е4)). Для того чтобы машина Тьюринга функционировала, она должна следовать определенному протоколу, словно офисный служащий. Всякий раз, когда служащий выполняет свою работу, он совершает определенную последовательность действий, и после завершения одного шага он должен знать, каким будет следующий. Подобным образом каждый раз, обработав символ на ленте, машина Тьюринга должна до начала обработки следующего символа актуализировать свое состояние.

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

Для того чтобы машина Тьюринга могла менять состояние, используется таблица, названная таблицей переходов, которую обозначим символом Д. В соответствии с этой таблицей, используя правила перехода, или функции, машина после завершения одной операции переходит к следующей. Таким образом, обратившись к таблице, машина Тьюринга после завершения операции актуализирует свое состояние. Каждый раз, когда головка для считывания/записи находит на ленте символ, она соотносит его с символом, описывающим собственное состояние машины и указывающим, что она должна сделать далее для каждой комбинации символов. То есть в таблице представлено состояние ячейки и состояние машины, А х Q. В соответствии с этой комбинацией по таблице определяются следующее состояние Q и новый символ А, который будет записан на ленте вместо считанного, а также то, в каком направлении должно будет перемещаться устройство по ленте: вправо (П) или влево (Л). Таким образом, в самом простом виде работа машины Тьюринга определялась тремя элементами: состоянием машины Q, алфавитом А и таблицей А, в которой собирается информация о каждом завершенном шаге машины Тьюринга для выполнения следующего.

Для того чтобы понять, как функционирует машина Тьюринга, приведем простой пример с тремя состояниями Q = {Е1, Е2, ЕЗ} и лентой памяти, ячейки которой могут содержать символы А = {0, 1}. Будем считать начальное состояние 1₀ равным Е1, головка считывания/записи находится во второй ячейке слева от рассматриваемого участка ленты, например имеющего вид 011110. Если таблица переходов сформирована тремя таблицами ниже, по одной на каждое из состояний El, Е2 и ЕЗ, то как будет вести себя машина?

Читая таблицу переходов и учитывая, что каждая операция реализуется в единицу времени (t₀, t₁, t₂,...), получаем, что начальное положение t₀ имеет следующий вид.

Согласно таблице переходов и учитывая, что машина в начальный момент времени t₀ находится в состоянии Е1, символ на ленте 1, в ячейке будет записан 0, шаг в следующую ячейку справа, состояние изменится на ЕЗ.

Действия машины для следующего момента времени t₁, когда она будет находиться в состоянии ЕЗ, указаны в таблице переходов. Затем, после того как головка считает в ячейке символ 1, машина перейдет в состояние Е2, в ячейке будет записан 0, шаг в следующую ячейку вправо.

После завершения предыдущей операции наступит момент времени t₂. Так как машина находится в состоянии Е2 и из ячейки считывается 1, то, следуя указаниям таблицы переходов, в ячейку будет записано 1, устройство перейдет вправо, и машина изменит состояние на Е1.

Последний момент времени, t₄. Машина находится в состоянии Е1, в считываемой ячейке стоит символ 1. Согласно таблице переходов, в ячейку будет записан 0, шаг вправо, переход в состояние ЕЗ.

Одним из ограничений машины Тьюринга является то, что она ведет себя как компьютер, выполняющий единственный алгоритм, то есть способный реализовывать только одну задачу. С исторической точки зрения одной из первых машин Тьюринга стала система AGC (Apollo Guidance Computer — бортовой управляющий компьютер миссии «Аполлон»). Эта машина была главным бортовым компьютером миссий NASA, позволивших совершить доставку человека на Луну 20 июля 1969 года. Задолго до этой эпопеи, осознавая присущее его машине ограничение, Алан Тьюринг сделал расширение своей машины, назвав результат универсальной машиной Тьюринга, или у-машиной. Речь идет о машине Тьюринга, которую можно использовать в виде любой другой машины Тьюринга, то есть способной обрабатывать другие алгоритмы. Таким образом, компьютер — это пример универсальной машины Тьюринга. Еще один пример — смартфоны, или мобильные телефоны, работающие как мини-компьютер.

Один из самых интересных примеров машины Тьюринга — миникомпьютер миссий «Аполлон», организованных NASA для доставки человека на Луну. Это была машина Тьюринга, разработанная в Массачусетском технологическом институте для навигации и прилунения. Среди множества мини-компьютеров, созданных для разных миссий, AGC (Apollo Guidance Computer — бортовой компьютер «Аполлона») был самым популярным. Программа, с помощью которой можно моделировать работу мини-компьютера миссий «Аполлон», а также выполнять современные программы, написанные для Windows, Linux, Mac Os или другой операционной системы, называется Virtual AGC. Она написана на Ассемблере, низкоуровневом языке программирования, в связи с тем что память мини-процессора AGC — всего 38912 символа длиной 15 бит (последовательность 15 единиц и нулей). Программа моделирует виртуальный компьютер в машине AGC, выполняющий программу, хранящуюся в его памяти. На лунном модуле мини-компьютер AGC использовал программу Luminary, в то время как на командном модуле применялась программа Colossus. Обе они доступны на симуляторе.

Модель мини-компьютера миссий «Аполлон» на эмуляторе Virtual AGC.

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

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

— Во-вторых, шаги или правила должны быть определены четко и однозначно. Приведем простой школьный эксперимент для «измерения числа я»: 1) обмотайте банку бумажной лентой, лишний материал ленты обрежьте; 2) снимите бумажную ленту и измерьте ее длину; 3) поместите банку между двумя книгами и измерьте расстояние между краями книг, соприкасающимися с банкой, для получения диаметра; 4) вычислите частное длины и диаметра. Полученная величина и будет я.

— В-третьих (хотя это требование является дополнительным), желательно, чтобы с помощью алгоритма можно было решить не только конкретную задачу, но все задачи подобного класса, например расставить слова по алфавиту.

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

Например, процедура стирки состоит из следующих шагов.

— Шаг 1. Разобрать одежду по цветам. Белые вещи и вещи светлых тонов должны стираться отдельно от цветных и темных вещей.

— Шаг 2. Прочитать этикетки на одежде, чтобы выяснить максимальную температуру и способ стирки (а также сушки, глажки и так далее).

— Шаг 3. Насыпать в лоток стиральной машины порошок.

— Шаг 4. Уложить одежду в стиральную машину. Выбрать соответствующую программу и температуру.

— Шаг 5. Достать выстиранную одежду.

— Шаг 6. Конец программы.

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

— Шаг 1. В обоих выражениях выделить одну неизвестную.

— Шаг 2. Уравнять выражения.

— Шаг 3. Решить уравнение.

— Шаг 4. Подставить полученную величину в одно из двух уравнений, где выделена одна неизвестная.

— Шаг 5. Решить получившееся в предыдущем пункте уравнение.

— Шаг 6. Конец программы.

Эти заключения приводят нас к выводу о том, что компьютер представляет собой машину Тьюринга, работающую с алгоритмами. Когда решение задачи может быть выражено в виде алгоритма, считается, что задача разрешима. Швейцарский инженер Никлаус Вирт (р. 1934), автор языков программирования «Алгол», «Модула-2» и «Паскаль», участвовал в разработке определения программы в 1975 году. Согласно его определению, программа — соединение алгоритма с формой организации данных внутри программы; организация данных также получила название структура данных. Отсюда происходит знаменитое выражение Вирта: алгоритм + структура данных = программа.

Несмотря на то что с Тьюрингом всегда ассоциировалась машина, носящая его имя, после того как с трудами этого исследователя познакомился другой замечательный математик, Алонзо Чёрч (1903-1995), последний опубликовал работу, которая отнимала у машины Тьюринга часть оригинальности.

В 1930-е годы Чёрч вместе со Стивеном Клейни (1909-1994) ввели Х-исчисление — абстрактную математическую систему для формализации и анализа вычислимости функций.

Функция — математическое выражение у = f(x), отражающее связь между двумя переменными, например длиной х и весом у синих китов, в виде выражения у = 3,15х - 192. Это понятие, предложенное в XVII веке Декартом, Ньютоном и Лейбницем, в 1930-е годы было пересмотрено с целью разработки общей теории математических функций.

Одной из заслуг Чёрча считается введение нового синтаксиса для представления данного класса математических выражений. Так, если, например, мы вычислим значение выражения (+(*23)(*56)), при этом звездочка — оператор умножения, то получим 36, поскольку (2 · 3) + (5 · 6) = 6 + + 30 = 36. Математическая функция должна быть абстрактной. Также для λ-исчисления используется более сложное выражение (λx. + x1), означающее: «Функция (представленная символом λ) от переменной (здесь х), которая имеет вид λ(x) (представлена здесь как.), добавляет (оператор +) величину переменной (то есть х) к 1». Мы можем несколько усложнить предыдущее выражение, записав ((λ х. + х1)3), результат которого равен 4, поскольку мы указали, что х = 3. Предсказуемо, что для преобразования всех элементов λ-исчисления мы можем усложнять операции. Другой заслугой такого типа исчисления стало его влияние на теорию, изучающую компьютерное программирование.

Однако если λ-исчисление и получило известность, то только благодаря тому, что Чёрч использовал эту абстракцию для изучения проблемы остановки, придя в результате к понятию разрешимой задачи, то есть идеи, лежащей в основе машины Тьюринга. В свою очередь, Тьюринг в 1937 году доказал, что λ-исчисление и его машина эквивалентны, то есть представляют собой два пути, по которым можно прийти к одному результату. Когда машина Тьюринга обрабатывает одно из указанных выражений, например (+31), она останавливается после того, как получен результат, в данном случае 4, то есть эта задача является разрешимой. С практической точки зрения λ-исчисление вдохновило развитие так называемых функциональных языков программирования, одним из примеров которых является «Лисп» — важнейший язык искусственного интеллекта. Появился он в 1958 году благодаря Джону Маккарти (1927-2011), автору термина «искусственный интеллект». Среди характеристик, которые язык унаследовал от λ-исчисления, — использование скобок:

(defstruct persona

(имя Alan)

(возраст 41))

или более просто:

(format t «Привет, Тьюринг!»)

В 1982 году нобелевский лауреат в области физики Ричард Фейнман (1918-1988) выдвинул захватывающую задачу, к которой мы обратимся в последней главе. После обнаружения ограничений в вычислительных способностях машин Тьюринга, помимо известной проблемы остановки (поговорим о ней в следующем параграфе), Фейнман предсказал существование вопросов, которые никогда не смогут быть обработаны компьютером. Он предположил, что и машины Тьюринга, и компьютеры не могут применяться для моделирования явлений квантовой природы, наблюдаемых на уровне атомов и не соответствующих классической физике. Ученый хотел сказать, что квантовые явления относятся к неразрешимым задачам, следовательно, они не могут быть обработаны обычным компьютером: машина Тьюринга, помимо прочих особенностей, должна для этого находиться одновременно в разных состояниях или одновременно считывать данные из разных ячеек. Компьютер для обработки квантовых явлений должен быть способным воспринимать не только состояния 0 и 1, но и возможные средние значения между 0 и 1 и одновременно использовать разные регистры оперативной памяти. После этого, в 1985 году, другой английский физик израильского происхождения, Дэвид Дойч (р. 1953), разработал новый класс машины Тьюринга, в котором эти ограничения были преодолены, — квантовую машину Тьюринга. Квантовые компьютеры способны моделировать неразрешимые задачи, такие как квантовые феномены, и, естественно, их ждет широкое применение.

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

Курт Гёдель (1906-1978), создатель теоремы о неполноте, пошатнувшей основы математики.

Деталь машины Тьюринга, построенной из деталей конструктора LEGO.

Алан Тьюринг участвует в забеге на длинную дистанцию в Доркинге (Англия) в 1946 году. В этом забеге он занял второе место.

Также возможна машина Тьюринга, считывающая информацию из ячеек на нескольких лентах. Предлагались и другие альтернативы, например индетерминистская машина Тьюринга, в которой таблица переходов предусматривает для определенного состояния несколько правил перехода, и их выбор происходит случайно. Однако настоящим вызовом стал класс машин, которые Тьюринг назвал оракулом, или о-машиной. В этой разработке ученый попытался преодолеть ограничения традиционной машины, обеспечив ее достаточной вычислительной мощностью для решения проблемы остановки или задач, решение которых невозможно было выразить с помощью алгоритма. О-машина — это машина Тьюринга, подключенная к черному ящику, называемому оракулом и позволяющему преодолевать ограничения машины. Оракул можно представить как вторую ленту. В этой машине вводится специальный знак — маркер. Между маркерами помещается символ, по которому машине требуется консультация оракула. Дойдя до него, машина Тьюринга переходит в специальное состояние, названное состоянием вызова, и направляет оракулу запрос. Если оракул признает символ принадлежащим к его системе символов, машина переходит в состояние 1, в противном случае — в состояние 0. Оракул стал первой попыткой исследований Тьюринга в области, которая впоследствии получит название гипервычислений, или сверхтъюринговых вычислений y, то есть вычислений, находящихся за пределами возможностей компьютера, предложенного самим английским ученым.

После создания машины Тьюринга английский ученый стал изучать проблему разрешения (по-немецки — EntscheidungsproЫетп) с помощью собственной концепции, известной с тех пор как проблема остановки. Проблема состоит в том, чтобы предсказать, остановится машина Тьюринга, «зависнет», как это делают современные компьютеры, или продолжит работать после считывания очередного символа. Таким образом, вопрос, на который пытался дать ответ Тьюринг, состоял в возможности применения механического процесса (специальной программы) для определения, остановится ли другая программа при получении на входе определенной величины или данных. Сегодня на любом компьютере можно легко повторить некоторые простые опыты по этому и другим вопросам, над которыми работал Тьюринг. Учитывая сходство между машиной Тьюринга и компьютером, на котором выполняется программа, решение проблемы будет состоять в ответе на вопрос, остановится выполнение программы или она будет выполняться бесконечно. Рассмотрим эти две ситуации со следующими программами на языке BASIC-256. Так, эта программа остановится после выполнения

print «Привет, Тьюринг!»,

а вторая будет выполняться вновь и вновь без остановки:

r=true

while г

print «Привет, Тьюринг!»

end while

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

Предположим, мы даем название остановка (кандидат, вход) программе, способной выяснить, остановится ли выполнение другой программы, которую мы назвали кандидат; произойдет ли остановка при получении определенных входных данных, которые мы назовем вход. Действительно, если мы представим программу остановка (кандидат, вход) в форме псевдокода, получим

Программа остановка (кандидат, вход)

if input = вход и кандидат → остановится

then остановка (кандидат, вход) = истина

if input = вxoд и кандидат → не остановится

then остановка (кандидат, вход) = ложь;

Представим, что, используя программу остановка (кандидат, вход), мы пишем другую программу, которая называется парадокс (вход):

программа парадокс (вход)

if остановка (кандидат, вход) = ложь

then return истина

else return ложь

Сделаем в наших рассуждениях еще один шаг и вслед за Тьюрингом обозначим через Р программу парадокс. Далее выполним программу остановка (Р, Р). Если программа, вложенная в главную, вернет ответ «Ложь», значит, программа Р не останавливается, получив в качестве входных данных программу, идентичную себе самой, тогда основная программа парадокс (Р), вернув значение « Истина», должна остановиться, но это невозможно и, значит, ложно.

Напротив, если программа остановка (Р, Р) вернет ответ «Истина», так как программа Р остановит свое выполнение, получив в качестве входных данных величину Р, тогда программа парадокс Р не остановится, возвращая значение «Ложь». Принимая во внимание все противоречия, Тьюринг сделал вывод, что программа остановка (или halt) не позволяет оценить Р. Другими словами, проблема остановки неразрешима.

Хотя и не существует программы, которая служила бы универсальным инструментом для удовлетворительного решения проблемы остановки, ученые решили, что можно написать программу, дающую ответы на отдельные случаи, то есть, говоря современным языком, частные программы. Этот класс программ был назван программами PHS (partial halting solver), или программами, частично решающими проблему остановки. Однако со временем ситуация была сочтена такой же неразрешимой, как и с проблемой остановки. Вновь используя язык BASIC-256, напишем программу, которая получает на вход программу Р$. Задача состоит в получении на выходе (output) сообщения о том, останавливается ли выполнение программы Р$:

input Р$

if Р$ = "halt" then

print «программа останавливается ДА»

else

print «программа останавливается НЕТ»

endif

end

Мы приходим к поистине разочаровывающему выводу: нет уверенности, что такая простая с виду программа вернет пользователю корректный результат. Удивительно, что еще до появления компьютера и программного обеспечения Тьюринг смог прийти к выводу, что не существует механической процедуры, то есть машины Тьюринга или современной компьютерной программы, которая могла бы определить, остановится ли другая программа (или машина Тьюринга), получив на вход определенные данные. Этот вывод Тьюринг получил с помощью собственного изобретения — машины Тьюринга. Это еще раз доказывает гениальность ученого, который за свою короткую жизнь смог стать величайшим человеком XX века.

Современный компьютер можно считать машиной Тьюринга, имеющей внутри себя еще одну такую машину. Для пояснения этой идеи приведем в пример один из первых компьютеров, ENIAC (Electronic Numerical Integrator And Computer). Этот мастодонт начала компьютерной эры может быть представлен как машина Тьюринга с тремя лентами: одна лента — для считывания входных данных, другая — для записи и возвращения результата, а третья выполняла роль памяти.

В современном компьютере машина Тьюринга, имевшаяся в ENIAC, должна быть изменена, принимая во внимание, что входящая лента раздваивается на вспомогательную память (например, жесткий диск, SD- или флеш-карта) и клавиатуру. В такой машине в виде ленты выхода можно представить монитор, лента памяти соответствует RAM (ОЗУ). Если мы будем рассматривать операционную систему (разные версии Windows Microsoft, или Linux/Unix, или Mac OS) как машину Тьюринга, получится, что совокупность программ, позволяющих управлять ресурсами компьютера, — это машина Тьюринга, контролирующая другую такую же машину, которой является сам компьютер. Кроме того, когда программист пишет программу — совокупность инструкций, то есть исходный код, — он, в свою очередь, должен перевести эти инструкции в машинный или двоичный вид с помощью компилятора, который также можно считать машиной Тьюринга. После преобразования программа может быть выполнена микропроцессором — важнейшим устройством в компьютере. Лежащая в основе всего модель представляет и компьютер, и программу, с помощью которой мы переводим программы на язык, делающий возможным их выполнение, и операционную систему как машины Тьюринга. Другими словами, «все это программы, все это software», к которым нужно добавить электронные схемы, hardware, как будто бы речь идет о software, — эта важная идея является следствием разработок Тьюринга.

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

Одна из первых моделей появилась в 1972 году в Университете Брандейса в Массачусетсе (США). Ее создатель Ира Гилберт преследовал цель обучать студентов основам информатики. Чуть позже появилось несколько версий машины Тьюринга из деталей LEGO. С помощью соединяющихся друг с другом пластиковых кубиков Денис Кузено построил машину Тьюринга, хотя эта модель не была полностью автоматизирована. Для хранения в программируемом микроконтроллере таблицы переходов в ней применялись «умные» кубики LEGO RCX, использующиеся любителями-робототехниками. Еще одна модель машины Тьюринга была построена с помощью LEGO японцем Джо Нагатой. В 2010 году Майк Дейви создал винтажную модель в память о машине, описанной в работе Тьюринга, которая была опубликована в 1936 году. В его устройстве были использованы микроконтроллер Parallax Propeller и SD-карта, на которой хранились данные о состояниях машины.

Все эти примеры показывают, что практическая реализация на уровне hardware машины Тьюринга не так проста. В то же время существует немало примеров моделирования машины Тьюринга с помощью software, в основном потому что такой вариант гораздо доступнее. Среди самых интересных проектов можно назвать «Turing and Post Machines: C++ Simulators» — подборку программ на языке C++ для моделирования машины разных типов (детерминистской, индетерминистской, универсальной, с ошибками, с разными лентами и др.); симулятор Visual Turing, разработанный для операционной системы Windows и позволяющий увидеть в действии разные машины Тьюринга. Еще один пример простой машины Тьюринга на языке Java называется tmsimbgm. Существует оригинальная программа jkturing Джона Кеннеди из Университета Санта-Моники (США), созданная для операционной системы MS-DOS и обновленная для разных версий Windows, хотя этот вариант моделирования несколько более скромный, чем Visual Turing или Jflap. Очень любопытна модель Uber Turing Machine 2011 года, включающая алфавит для написания алгоритмов. Все эти программы вызывают интерес, потому что представляют собой варианты моделирования машины Тьюринга на универсальной машине Тьюринга — компьютере.

Одной из самых интересных задач является возможность создать машину Тьюринга, используя другую машину — игру «Жизнь». Этот автомат был придуман в 1970 году Джоном Хортоном Конвеем (р. 1937), профессором Кембриджского университета, где учился и Тьюринг. Речь идет о модели компьютера, которая была очень популярна среди любителей науки, особенно после того, как ее описал популяризатор математики Мартин Гарднер (1914-2010) в журнале Scientific American. Игра представляет собой клеточный автомат, то есть двумерную решетку, клетки которой заполнены конечными автоматами, также известными как машины конечных состояний. Речь идет об объекте, находящемся в одном из множества состояний, при этом данное множество конечно. Например, светофор может находиться в течение некоторого времени t в состоянии «зеленый», то есть в одном из трех возможных (красный, желтый, зеленый). Другой пример — нейрон, который может находиться в состоянии покоя или возбуждения. В машине Тьюринга, использующей для моделирования клеточный автомат, с течением времени (ί) состояния каждого конечного автомата обновляются. Обновление или расчет, каким будет состояние в следующий отрезок времени (£ + 1), происходит в соответствии с набором правил, известных как правила перехода, меняющие состояние каждого конечного автомата с учетом его актуального состояния и состояний соседних автоматов.

В конце XX века несколько ученых и любителей науки задались вопросом: можно ли построить машины Тьюринга с помощью игры «Жизнь»? Поль Рендель 2 апреля 2000 года создал модель машины Тьюринга с помощью клеточного автомата Джона Хортона Конвея, а 10 февраля 2010 года повторил свой замечательный опыт. В первой модели использовалась решетка 1714 х 1647, с помощью конечных автоматов которой была создана машина Тьюринга. Она имела три возможных состояния и могла обрабатывать на ленте памяти три разных символа. В эксперименте 2010 года была создана модель универсальной машины Тьюринга. Возможность моделирования машины Тьюринга с помощью игры «Жизнь» привела к удивительному выводу: игра «Жизнь» имела аналогичные с компьютером возможности. Более того, любое природное явление, например формирование колец Сатурна или взаимодействие зайцев и волков, можно смоделировать с помощью компьютера. Существуют и другие успешные примеры создания машин Тьюринга с помощью игры «Жизнь», некоторые из них даже получили собственные названия: MRM (Minsky Register Machine) или ее универсальная версия URM, а также CoreWorld, LogiCell и другие.

Один момент из игры «Жизнь».

В игре «Жизнь» каждый конечный автомат граничит с восьмью клетками, окружающими его в направлениях С, Ю, В и 3, а также по диагонали: С-В, Ю-В, Ю-3 и С-3. Считается, что для всех конечных автоматов возможны только два состояния: состояние 0 («мертвые клетки») и состояние 1 («живые клетки»); каждому из них соответствует свой цвет. Состояния конечных автоматов актуализируются с применением следующих правил перехода.

— Правило 1: если состояние конечного автомата α^t_ij 0 или 1, его следующее состояние, а именно α^t+1_ij, будет таким же, как предыдущее, если количество соседних клеток в состоянии 1 равно 2:

α^t+1_ij ⁼ α^t_ij, если сумма соседних клеток (α^t_ij) = 2.

— Правило 2: конечный автомат перейдет в состояние 1, если количество соседних клеток в состоянии 1 равно 3, изменение состояния автомата произойдет только при условии, что его состояние было 0 во время t. В противном случае состояние останется равным 1:

α^t+1_ij = 1 если сумма соседних клеток (α^t_ij) = 3.

— Правило 3: описывает изменения при разном количестве соседних автоматов, находящихся в состоянии 1. Если количество автоматов рядом в состоянии 1 меньше 2 (то есть один или ни одного) или более 3 (четыре, пять, шесть, семь или восемь), конечный автомат «умирает», принимая значение 0. В этом случае изменение состояния происходит, только если во время t его состояние было 1, в противном случае состояние не будет изменено и останется равным 0:

если сумма соседних клеток (α^t_ij) < 2

α^t+1_ij = 0

или сумма соседних клеток (α^t_ij) > 3.

При каждой итерации и применении правил перехода к каждому конечному автомату клеточный автомат эволюционирует, при этом появляются рисунки, характерные для данной игры. Образующиеся формы до сих пор вызывают восхищение среди компьютерных любителей. Существует большой выбор программ, позволяющих попробовать игру «Жизнь» (Life32, Xlife 2.0, Life 1.05/1.06, Pro Life, Mcell, dbLife и другие), из них самой впечатляющей является Golly.

В августе 1936 года Алан Тьюринг направил для публикации в Proceedings of the London Mathematical Society статью под названием «О вычислимых числах, с приложением к проблеме разрешимости». Мы уже говорили о ней, так как именно в этой работе впервые упоминалась машина Тьюринга. Также в статье даются определения понятиям «вычислимое» и «невычислимое» и представлены фундаментальные идеи математики и информатики. По воле случая в том же году Алонзо Чёрч опубликовал в журнале American Journal of Mathematics статью «Одна неразрешимая проблема элементарной теории чисел»; оба ученых разными путями пришли к одним результатам. Ход рассуждений Тьюринга был довольно оригинальным: он рассматривал класс операций, которые в реальном мире мог «механически» выполнять человек (например, клерк, осуществляющий одну и ту же задачу вновь и вновь) или машина (суммируя два числа). Ход рассуждений Чёрча был классическим для абстрактного мира, что традиционно для математики. К сожалению, Тьюринг опубликовал свою статью чуть позже, и это лишило его работу исключительности, так как ему приходилось ссылаться на статью американца. Однако обе статьи представляют теоретические основы создания машины, позже названной компьютером.

Месяц спустя, в сентябре 1936 года, Тьюринг отправился в США. Там он планировал получить докторскую степень и провести два года в Институте перспективных исследований в престижном Университете Принстона. Под руководством Алонзо Чёрча Тьюринг обратился к теме, странной даже сегодня — использованию в математике интуиции. Не теряя времени на философские объяснения, скажем, что интуиция может быть определена как продукт здравого смысла. То есть речь шла о предвосхищении или ментальном видении, которое помогает нам при рассуждениях прийти к умозаключению. Учитывая, что в ходе рассуждений мы связываем факты в логическую цепь, интуиция представляет собой дополнительный компонент, необходимый для разрешения задачи.

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

Алан Тьюринг, «Логические системы, основанные на ординалах»

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

В этот период Тьюринг начал проявлять интерес к возможности создания своей машины, но эта цель так и не была достигнута. Именно во время пребывания в США проявился интерес ученого к hardware и, следовательно, к возможности создания с использованием электронных схем и электромеханических компонентов того, что еще недавно было не более чем интеллектуальным упражнением. И вновь, как и в случае появления идеи о машине Тьюринга на логическом уровне, мы сталкиваемся с тем, что ученый начал думать о реализации своей машины в эпоху, когда еще не было компьютеров. Он создал машину для умножения с использованием электромагнитных реле, которая позволяла умножать двоичные числа (то есть числа, которые можно представить с использованием только двух знаков: 0 и 1).

В 1938 году еще один гениальный исследователь той эпохи, американский ученый венгерского происхождения Джон фон Нейман предложил Тьюрингу временную должность в Принстонском университете. Однако тот отверг это предложение и летом того же года вернулся в Королевский колледж. По возвращения он занялся созданием аналогового механизма для оценки так называемой гипотезы Римана.

В августе 1939 года Тьюринг получил предложение работать в Блетчли-парке над расшифровкой перехваченных сообщений нацистов.