Lahoz-Beltra Rafael

Размышления о думающих машинах. Тьюринг. Компьютерное исчисление

Rafael Lahoz-Beltra

Наука. Величайшие теории. Выпуск 15: Размышления о думающих машинах. Тьюринг. Компьютерное исчисление

Наука. Величайшие теории Выпуск № 15, 2015 Еженедельное издание

Пер. с йен. — М.: Де Агостини, 2015. — 152 с.

ISSN 2409-0069

© Rafael Lahoz-Beltra, 2012 (текст)

© RBA Collecionables S.A., 2012

© ООО «Де Агостини», 2014-2015

Введение

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

Задача нашей книги — объяснить, не отступая от истины и при этом в доступной форме, сущность его фундаментального вклада в развитие современного мира.

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

Разносторонний характер исследований Алана Тьюринга подчеркивает его гениальность. Способность ученого находить новые объекты для исследования, видеть связи между явлениями и вопросами, которые, на первый взгляд, могут показаться совершенно разными, позволяет его сравнить разве что с Джоном фон Нейманом. Именно с этими двумя именами связано появление в 1940-х годах понятия «междисциплинарный исследователь», то есть ученый, способный с использованием математики и компьютеров выделить общие элементы в биологии, экономике, социологии, физике с целью унификации, казалось бы, различных, но сходных но сути проблем.

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

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

Глава 2 описывает, как атаки немцев в годы Второй мировой войны привели британцев к созданию Блетчли-парка, в котором криптографы, включая Тьюринга, смогли расшифровать перехваченные сообщения Третьего рейха. В эти годы талант ученого полностью раскрылся, и он, как и многие его коллеги, получил достойные награды в конце войны. Именно в Блетчли-парке появился на свет Colossus («Колосс»), который считается первым в мире компьютером. Во Второй мировой войне люди гибли без счета, но также бессчетны и достижения человеческого разума в этот период. Напряженная работа, ставшая бесценным опытом, подготовила ученого к решающему шагу от абстрактного мира машины, носящей его имя, к созданию реального компьютера Pilot АСЕ («Туз»).

В главе 3 рассматривается вопрос, споры по которому не утихают по сей день: кто изобрел компьютер — британцы или американцы? Согласно принятой версии, ученые Соединенного Королевства благодаря разработке Colossus обеспечили своей стране первенство в создании компьютеров. Но почему же США сегодня занимают лидирующие позиции в этой индустрии?

После описания характеристик Pilot АСЕ и ответов на вышеупомянутые вопросы мы углубимся в архитектуру фон Неймана, то есть принцип, согласно которому компоненты компьютера работают на логическом и функциональном уровне, а закончим рассказом о том периоде, когда Алан Тьюринг посвятил себя программированию компьютеров в Манчестерском университете.

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

Последний этап жизни ученого был так же плодотворен с научной точки зрения, как и первый. Именно в последние годы жизни он впервые использовал компьютер для изучения и моделирования биологических проблем, разработал математические модели роста и формирования живых организмов, пытаясь найти ответ на вопрос, как формируются полоски на шкуре зебры. В результате этих исследований возникла новая дисциплина — математическая биология. Весной 1954 года, в возрасте 41 года, Алан Тьюринг покончил с собой, съев отравленное яблоко.

В главе 5 детально рассматривается научное наследие Тьюринга. По очевидным причинам мы не говорим о современных компьютерах или суперкомпьютерах — ни о десктопах, ноутбуках, нетбуках или планшетах, ни об аппаратах, в основе которых лежит компьютер, таких как мобильный телефон, электронная записная книжка и другие. Все эти устройства являются результатом естественной эволюции теоретической машины Тьюринга и первых компьютеров — Colossus, ENIAC, Pilot АСЕ, EDSAC: все их версии можно перечислять бесконечно. В наследие Тьюринга можно включить не только сто вклад в развитие науки, гениальные находки и работы но информатике, но и все то, что было оставлено без завершения в его бумагах и вдохновило следующие поколения исследователей. Так, на стадии разработки находились квантовый компьютер, модели искусственных нейронных сетей и их использование в интеллектуальных системах в повседневной жизни, изучение молекулы ДНК с помощью компьютеров (структура ДНК была открыта Уотсоном и Криком за год до смерти Тьюринга).

Маршрут, по которому прошел в XX веке один из самых интересных и гениальных умов, осмысливший разумные машины, захватывает, а интерес к личности этого ученого и через пол века после его смерти продолжает расти.

1912 23 июня в Лондоне родился Алан Мэтисон Тьюринг, второй сын Юлиуса Мэтисона Тьюринга и Этель Сары Стони.

1926 После успешной сдачи вступительного экзамена его принимают в частную школу Шерборна.

1931 Поступает в Королевский колледж Кембриджа, где изучает математику.

1935 Получает двухлетнюю стипендию для работы в Королевском колледже.

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

1939 В качестве криптографа начинает сотрудничество с Блетчлн-парком. Придумывает Bombe — машину, позволившую британцам успешно расшифровывать код «Энигмы».

1945 Получает орден Британской империи за вклад в победу британцев во Второй мировой войне. Переезжает в Национальную физическую лабораторию в Лондоне, где берет на себя задачу по созданию компьютера Pilot АСЕ, схему которого он представил в лаборатории в 1946 году.

1948 Начинает работу в Манчестерском университете, где вместе с Максом Ньюманом организует лабораторию по разработке и конструированию компьютеров для научного использования.

1950 Публикует статью «Компьютерное оборудование и интеллект», где вводит тест Тьюринга. Речь идет о фундаментальном испытании для оценки поведения компьютера, программы или машины. Программирует компьютер MADAM Манчестерского университета и для этого пишет ему любовные письма.

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

1954 В возрасте 41 года Тьюринг совершает самоубийство, съев яблоко, отравленное цианидом.

Глава 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/3 + x^5/5 - x^7/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, соответствующее записи в реестре при запуске машины в работу.

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

СОСТОЯНИЯ МАШИНЫ

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

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

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

Символ ленты

Записанный символ

Переход

Следующее состояние

0

1

Л

Е2

1

0

П

ЕЗ

Символ ленты

Записанный символ

Переход

Следующее состояние

0

0

Л

ЕЗ

1

1

П

Е1

Символ ленты

Записанный символ

Переход

Следующее состояние

0

1

Л

Е1

1

0

П

Е2

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

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

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

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

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

У-МАШИНА ТЬЮРИНГА. МОЖЕТ ЛИ МАШИНА БЫТЬ УНИВЕРСАЛЬНОЙ

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

ЛУННАЯ МИССИЯ «АПОЛЛОН-11»

Один из самых интересных примеров машины Тьюринга — миникомпьютер миссий «Аполлон», организованных 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: если состояние конечного автомата αtij 0 или 1, его следующее состояние, а именно αt+1ij, будет таким же, как предыдущее, если количество соседних клеток в состоянии 1 равно 2:

αt+1ij = αtij, если сумма соседних клеток (αtij) = 2.

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

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

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

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

αt+1ij = 0

или сумма соседних клеток (αtij) > 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 года Тьюринг получил предложение работать в Блетчли-парке над расшифровкой перехваченных сообщений нацистов.

Глава 2

Машины против кода.

Тьюринг как криптограф

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

Битва за Атлантику, продлившаяся практически до последних дней Второй мировой войны, началась 3 сентября 1939 года. За этот период на театре военных действий были реализованы самые масштабные военные операции. На протяжении всего конфликта немецкие подлодки систематически атаковали британский торговый флот, затрудняя снабжение Британских островов. Во время Первой мировой войны также происходили неоднократные столкновения немецкого и британского флотов, но во Второй мировой войне сценарий операций кардинально изменился. Появился новый класс судов — субмарины, ставшие смертельным оружием против британцев, так что те вынуждены были формировать военное сопровождение для защиты торговых кораблей. Эта стратегия дала временный результат: немецкие подлодки тогда были очень медлительными, для осуществления выстрела им необходимо было подняться на поверхность, и в это время они становились легкой добычей. К концу войны Германия потеряла около 75 % своих подлодок. Однако действия немецкого подводного флота вызвали серьезные проблемы со снабжением Соединенного Королевства. Также с 1940 по 1941 год страна подвергалась серьезным бомбардировкам. Хотя их основной целью был Лондон, пострадали и другие города: погибло большое количество мирного населения и было разрушено более миллиона жилых домов.

БИТВА ЗА АТЛАНТИКУ

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

Стратегия Action in the North Atlantic, классическая игра-симулятор.

После окончания Первой мировой войны, 23 февраля 1918 года, немецкий инженер Артур Шербиус (1878-1929) запатентовал «Энигму», машину для шифрования сообщений. Фирма «Шербиус & Риттер», основанная изобретателем и его партнером, сразу же начала торговать устройством, однако позже права на его использование были проданы немецкому предприятию Chiffriermaschinen Aktien-Gesellschaft. В начале 1920-х годов «Энигма» была представлена публике в двух городах Европы, с тех пор начались продажи целого ряда моделей для гражданского использования. В своем названии они имели одну из букв: А, В, С, D. Изначально машина создавалась для шифрования информации о сделках, но пик ее использования пришелся на период войны. В Испании продавалась модель D, применявшаяся во время Гражданской войны. Самым важным клиентом производителей стала Германия. Для нее была разработана модель G; модель Funkschlussel, или М, стала использоваться на флоте, модель «Вермахт», или I, — в армии. Последняя разработка стала самой популярной, поэтому мы остановимся на пояснении принципа ее функционирования. В 1942 году свою модель стал использовать и немецкий подводный флот. Любопытно, что 40 % всех машин «Энигма» было изготовлено в годы Второй мировой войны. Для немцев эта машина стала жизненно необходимой, и Гитлер отдал приказ о включении ее в программу вооружения Третьего рейха.

ДЬЯВОЛЬСКАЯ МАШИНА. КАК РАБОТАЛА «ЭНИГМА»

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

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

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

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

Немецкие солдаты во время Второй мировой войны передают сообщения с помощью «Энигмы·.

Алан Тьюринг, фотография сделана в 1951 году.

Разные модели «Энигмы·.

Очевидно, что эти особенности успешно использовали британские криптографы в Блетчли-парке, где был построен большой комплекс для дешифровки перехваченных немецких радиосообщений. Кроме рефлектора, расположенного слева от роторов, справа от них находилось колесико входа, или стартер, соединявший клавиатуру, с помощью которой вводилось сообщение, с лампами, подсвечивавшими соответствующие буквы в исходящем зашифрованном сообщении. На фронтальной части «Энигмы» имелась коммутационная панель, позволявшая превращать одну букву в другую, помимо шифрования с помощью роторов. Если учесть все устройства, участвовавшие в трансформации одной буквы (коммутационная панель, роторы и рефлектор), количество возможных конфигураций определялось количеством перестановок разных устройств и достигало невероятной цифры 10^114. Это впечатляет, принимая во внимание, что человеческий мозг содержит 10^11 нейронов, а количество атомов во Вселенной оценивается как 10^80. Обладая такой чудовищной машиной, Германия чувствовала себя уверенно, и передача радиосообщений с военными приказами представлялась ей полностью безопасной. Однако обстоятельства сложились не в пользу неприступной «Энигмы», так как на захваченных немецких субмаринах были обнаружены несколько шифровальных машин и книг с кодами.

«БОМБЫ» ПРОТИВ «ЭНИГМЫ»

Польша, довольно сильно пострадавшая от нацистов, получила «Энигму» невероятным способом: машина была отправлена в Варшаву по почте из Германии. Благодаря этому группа математиков из кабинета криптографии бюро шифров (BS 4) Генштаба Польши под руководством Мариана Режевского (1905- 1980) смогла расшифровать сообщения, кодированные с помощью «Энигмы», а саму машину затем вернули отправителю. Поляки, а позже и представители других стран-союзниц обнаружили одну особенность шифровок: немцы в сообщениях в закодированном виде передавали начальное положение роторов, то есть указывали одну из 26 букв, которую можно было увидеть в специальном окошке. Например, если начальным положением ротора была буква В, в сообщении эта информация отображалась как ВВ. С 1932 года Режевский и его команда успешно расшифровывали перехваченные немецкие сообщения.

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

Но этот метод работал недолго. В 1938 году немцы добавили к машине еще три ротора, так что их общее количество достигло шести. Теперь полякам для успешной дешифровки сообщений требовалось около 60 «бомб». Экономических ресурсов для дальнейшей работы не хватало, и Польша приняла решение передать в 1939 году накопленные данные британской и французской разведкам. Британцы приняли вызов и создали GC&CCS (Правительственную школу кодирования и шифрования), расположенную в Блетчли-парке, рядом с Милтон- Кинс, городке вблизи Лондона. Группа польских криптографов отправилась во Францию, где они работали совместно с секретной французской службой до конца 1942 года, занимаясь дешифровкой немецких сообщений и переправляя данные в Блетчли-парк. После того как немцы захватили юг Франции, польские криптографы и сами через Испанию отправились в Соединенное Королевство. Польские историки считают, что британцы не оценили должным образом талант польских математиков.

ТЬЮРИНГ В БЛЕТЧЛИ-ПАРКЕ

В конце Второй мировой войны в Блетчли-парке насчитывалось 10 тысяч человек личного состава. Это был гигантский шпионский комплекс, работавший против нацистской Германии. Деятельность велась в разных отделах, размещенных в отдельных домиках-ангарах. В одном отделе технические специалисты и аналитики занимались перехватом сообщений немецкого правительства или армии, в другом шла дешифровка радиограмм, в третьем на основании дешифрованных сообщений пытались реконструировать сценарии военных операций или намерения немцев. Принимая во внимание, что немцы использовали разные сети связи, отделы также имели соответствующие подразделения, которые работали с разными конфигурациями «Энигмы» для каждой сети. С этой целью персонал Блетчли-парка присвоил каждой сети кодовые имена: Red (красный), Shark (акула), Chaffinch (зяблик).

В домике номер 8 (Hut 8) работал Алан Тьюринг, приглашенный в Блетчли-парк 4 сентября 1939 года, то есть на следующий день после объявления Британией войны Германии. Миссия ученого предполагала дешифровку кодов «Энигмы» немецкого подводного флота, активно участвовавшего в морской блокаде Британских островов. Как рассказывает британский историк Аса Бриггс (р. 1921), также работавший в Блетчли-парке с 1942 по 1945 год в домике б, среди сотрудников комплекса было много талантливых людей, но гением считался Алан Тьюринг. В этот период ученый ездил в США, чтобы организовать сотрудничество двух стран-союзниц. Существует мнение, что Тьюринг разрабатывал систему шифровки телефонных сообщений высшего руководства США и Соединенного Королевства, Рузвельта и Черчилля. При выполнении этого задания он сотрудничал с Дилли Ноксом (1884-1943), криптографом, получившим образование в Королевском колледже Кембриджского университета. Также они совместно занимались вопросом ускоренной автоматической расшифровки сообщений, кодированных с помощью «Энигмы». Предложенный метод оказался более эффективным, чем метод поляков, чьи знания о шифровальной машине были собраны в «Трактате об «Энигме» ( Treatise on Enigma).

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

В ходе войны в Британии была создана новая машина, в которой использовались идеи польской «бомбы», и она получила название Bombe[1 По одной из версий, оно происходит от названия десерта из мороженого Bombe glacee в виде шара или цилиндра. — Примеч. ред.]. Эта электромеханическая система воспроизводила работу группы машин «Энигма». Ее оригинальная версия была разработана Аланом Тьюрингом в 1939 году в Блетчли-парке, а построена Гарольдом Кином (1894-1973) из British Tabulating Machine Company (BTM) — предприятия, связанного с другим гигантом США, со временем получившим название IBM. В тот момент обе компании по разные стороны Атлантики занимались продажами табуляторов и машин для переписи населения. С помощью устройства, придуманного Германом Холлеритом (1860-1929), стало возможным чтение перфокарт, используемых для переписи: перфорация той или иной ячейки кодировала ответы. Существует версия, высказанная Эдвином Блэком в его книге «IBM и Холокост» (2001), что Адольф Гитлер закупил у IBM партию табуляторов, с помощью которых в 1933 году была сделана перепись еврейского населения Германии, и за это президент IBM Томас Уотсон (1874-1956) получил в 1937 году Орден Заслуг германского орла из рук самого фюрера.

Впоследствии Гордон Уэлчман (1906-1985) усовершенствовал оригинальную модель Bombe, поэтому окончательный вариант устройства известен как Bombe Тьюринга — Уэлчмана, в то время как польская машина-предшественница называлась криптологической бомбой (Bomba kryptologiczna). Окончательный вариант Bombe весил около тонны и включал 108 роторов, соединенных по три, что соответствовало трем роторам «Энигмы». В свою очередь, группы по три ротора соединялись в дюжины. Таким образом, машина состояла из трех отделов по 12 групп из трех роторов. Все эти роторы выполняли ту же работу, что и «Энигма», только в обратном направлении — для расшифровки сообщений. С механической точки зрения роторы имели ту же внутреннюю систему проводов, что и «Энигма»; рефлектор воспроизводился в довольно простом виде: контакты и провода были дублированы.

ПРОЕКТ SIGSALY

С конца 1942 года до весны 1943-го Тьюринг находился в США. Во время посещения лабораторий Белла он познакомился со знаменитым Клодом Шенноном (1916-2001), считающимся отцом современной теории информации. Хотя Тьюринг и мечтал поговорить с этим великим ученым о возможности создания искусственного интеллекта, в его задачу входил сбор идей для разработки системы шифровки голоса для защиты телефонных переговоров высших руководителей обеих стран, Рузвельта и Черчилля. Этот проект был назван SIGSALLY. Система шифровала голос с помощью так называемого случайного шума и часто использовалась союзниками во время войны. Любопытно, что SIGSALLY упоминается в научно-популярном романе «Криптомикон» (1999) Нила Стивенсона (р. 1959) в вымышленном разговоре двух персонажей: Лоуренса Ватерхауса и Алана Тьюринга. По окончании войны Тьюринг оставил Блетчли-парк и начал работать в Правительственном центре коммуникаций Ее Величества, где участвовал в создании переносного устройства для шифровки голоса Delilah. Для доказательства корректного функционирования системы во время шифровки и дешифровки использовалась запись голоса Уинстона Черчилля.

Процесс шифровки голоса

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

Машины системы шифрования голоса Delilah.

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

Кроме того, люди в зависимости от артикуляции по-разному произносят гласные, а в ходе нормализации эти различия устраняются. Затем нормализованный голос, наконец, шифруется. В процессе, разработанном Тьюрингом, фрагменты голоса нормализовались по шкале от 0 до 1. После нормализации фрагменты трансформировались с помощью арифметического оператора, модуля (мод). Этот оператор дает разницу от деления на целые числа: например, 5 мод 2 равно 1. В конце концов трансформированная таким образом волна голоса реконструировалась в обратной последовательности. Несмотря на высокий уровень разработки, эта система не нашла применения. Также интересно, что участие Тьюринга в обоих проектах осталось на втором плане, невзирая на его успехи во многих других исследовательских начинаниях.

Зашифрованное радиосообщение после перехвата превращалось во входные данные, Тьюринг принимал решение, каким должно быть соединение между группами по три ротора, по которым проходило сообщение до расшифровки, или выходных данных.

В Соединенных Штатах для армии также были созданы машины, выполнявшие сходные задачи, однако их конструкция была другой. Сами американцы считают, что их машины были более быстрыми, а crib-последовательности — более короткими по сравнению с английскими. Стандартная английская машина была эквивалентна 36 «Энигмам» и могла расшифровывать два или три сообщения одновременно. Для расшифровки она требовала выбора меню, где использовалось то, что англичане называли crib. Под этим понимался пример незашифрованного текста или сообщения, для которого имелось зашифрованное соответствие, например фрагмент перехваченного зашифрованного и расшифрованного текста. Для превращения crib в действенный инструмент нужно было хорошо знать немецкий военный жаргон, а также процедуру отправки сообщений. Очень важной стала информация о том, что «Энигма» никогда не шифровала букву, например А, самой собой. После выбора crib оператор Bombe разрабатывал меню, как показано в таблице ниже. Представим, что crib TURINGHABLAINGLES (ТЬЮРИНГГОВОРИТПОАНГЛИЙСКИ), а зашифрованный текст выглядит так (строка ЗТ): AIYLLVWPANNOZPOPE. Для того чтобы пример был более репрезентативным, мы использовали для шифровки текста модель «Энигмы» (http://www. bletchlypark.org.uk). На основании этих двух сообщений разработаем таблицу, в которой каждой букве зашифрованного текста будет соответствовать буква в оригинальном сообщении, или crib.

CRIB

т

и

R

1

N

G

Н

А

В

L

А

1

N

G

L

Е

S

ЗТ

А

1

Y

L

L

V

W

Р

А

N

N

O

Z

Р

O

Р

Е

П

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

ВБ

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

СБ

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

НБ

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

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

С помощью такой структуры оператор мог разработать меню для настройки конфигурации Bombe, а также начальные положения барабанов в верхней (ВБ), средней (СБ) и нижней части (НБ). После настройки конфигурации машина выполняла свою работу, останавливаясь каждый раз, когда обнаруживалось возможное решение, то есть расшифрованное сообщение. На схеме выше видны циклы, например ILO. Интересно, что Тьюринг заметил: чем больше циклов, тем меньше количество остановок и тем меньше неправильно расшифрованных сообщений. Общий внешний вид Bombe был достаточно привлекательным, барабаны были окрашены в разные цвета, представлявшие ротор «Энигмы», эмуляцией которого они являлись. Каждый барабан мог находиться в одном из 26 возможных положений, таким образом общее количество конфигураций было: 26x26x26 = 17576. Каждый раз, когда Bombe находила возможное решение, она останавливалась. Как правило, происходило это несколько раз, и машина выдавала

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

Первая модель Bombe была построена 18 марта 1940 года. В конце Второй мировой войны у британцев в Блетчли-парке было 211 Bombe, обслуживанием и эксплуатацией которых занималось около двух тысяч человек. Благодаря безоговорочному успеху, достигнутому с помощью этих машин, зажглась звезда Алана Тьюринга. Его работа как криптографа, а также весь комплекс Блетчли-парка сыграли значительную роль в военных событиях. Благодаря вкладу ученого стали известны даты авианалетов на Англию, маршруты немецких субмарин и кораблей; также Тьюринг сыграл важную роль в победе в Африке над корпусом маршала Роммеля и способствовал развертыванию операций союзников на западе Европы.

Несомненно, разработка Bombe стала одной из самых значительных работ Тьюринга как криптографа в ходе войны, но не единственной. Также ему принадлежат статистические процедуры для более эффективного использования Bombe, ставшие чрезвычайно актуальными при расшифровке немецких сообщений, кодированных «Энигмой». Эта техника получила название Banburismus. Кроме того, Тьюринг ввел новую процедуру, Turingery (шутливо Тьюрингизмус, или метод Тьюринга), которая облегчала расшифровку сообщений, кодированных другой адской машиной, Lorenz SZ 40/42. К концу войны Тьюринг, уже работая в Правительственном центре коммуникаций Ее Величества, создал переносную систему для шифрования телефонных сообщений, названную Delilah.

После окончания войны британский премьер-министр Уинстон Черчилль отдал приказ об уничтожении всех машин Bombe и соответствующих документов. На этом этапе жизни Тьюринг был связующим звеном между США и Соединенным Королевством. Именно тогда он начал думать о возможности создания разумной машины, что позже привело его к передовым находкам в области искусственного интеллекта. Также в эту эпоху ученый занимался электроникой и, вероятно, именно в Блетчли-парке осознал ее важность для будущего развития компьютеров.

В 1945 году, после окончания войны, Алан Тьюринг был награжден орденом Британской империи. Его гениальность признали, а также оценили его заслуги и вклад в качестве криптографа в победу.

Один из домиков Блетчли-парка, в котором персонал занимается расшифровкой кода «Энигмы».

Машина Bomba, разработанная Аланом Тьюрингом и построенная в Блетчли-парке Гарольдом Кином.

ЛОРЕНЦ — ЕЩЕ ОДНА АДСКАЯ МАШИНА

В начале Второй мировой войны британцы перехватили из немецкого лагеря сигналы, которые, к их удивлению, не использовали код Морзе и не были зашифрованы «Энигмой». Речь шла о сигналах машины Лоренца, соединенной с телетайпом, которой немцы также успешно пользовались.

В Блетчли-парке все немецкие сигналы телетайпа называли ключевым словом Fish («рыба»), а сигналы, кодированные машиной Lorenz SZ40/42, получили кодовое название Tunny («тунец»). Так же как это было в случае с «Энигмой», британцы смогли выяснить подробности работы машины Лоренца благодаря счастливой случайности и ошибкам немцев, хотя на этот раз сама машина в их руки не попадала. В Блетчли-парке была создана электромеханическая машина, использующая аналогичный принцип и способная расшифровывать сигналы машины Лоренца. Ее называли Tunny Machine («Машина-тунец»). Как же функционировал Lorenz SZ40/42? Когда записывался один знак, он трансформировался в другом коде — коде Бодо, придуманном в 1874 году и используемом с тех пор на телеграфе: в его основе лежит запись одного символа в виде последовательности пяти нулей и единиц, то есть пятибитный код. В ту эпоху 1 и 0 обозначались на ленте как «отверстие» и «интервал без отверстия». Машина Лоренца была оснащена особой механической системой, в ней несколько колесиков играли роль генератора случайных чисел, который используется при проведении любых розыгрышей, видеоигр, симуляций, шифровании и так далее.

Машина Lorenz SZ42.

Метод, используемый машиной Лоренца для шифровки сообщения, состоял в генерировании случайной пятибитной последовательности с помощью серии из 12 зубчатых колесиков (по-английски pinwheels), каждое из которых имело определенное количество контактов. Эти контакты могли быть в положении on(1) или off(0). Таким образом, при вращении получалась последовательность нулей и единиц, или бит. Если контакт был в активном состоянии, on, значение бита, соответствующего кодируемой букве, менялось: с 0 на 1, с 1 на 0. Когда контакт был в неактивном состоянии, off, значение сохранялось. Далее применялся булев оператор XOR («исключающее или») между каждым из битов знака и измененного знака. Таблица данного оператора может быть представлена в следующем виде.

А

в

A XOR B

0

0

0

0

1

1

1

0

1

1

1

0

Эта процедура повторялась несколько раз последовательно до трансформации исходного знака в другой в кодировке Бодо. Например, если мы хотим зашифровать фамилию TURING, сначала мы должны записать ее в виде кода Бодо. Получим последовательность 10000-00111-01010- -00110-01100-11010. Представим, что мы уже зашифровали последовательность знаков TURIN, а сейчас должны приступить к шифрованию последней буквы фамилии. Следующим шагом, если оператор машины настроил конфигурацию контактов диска, который мы назовем R1, как on-on-off-off-on, последовательность 11010, представляющая букву G, трансформируется в 00011, но такая последовательность соответствует букве А. Повторим эти шаги еще раз. Представим, что оператор машины настроил второй диск, который мы назовем R2, расположив контакты как on-off-on-off-on. В этом случае последний диск трансформирует последовательность 00011 и превратит ее в 10110, которая, согласно коду Бодо, соответствует Р. Таким образом, с помощью машины Лоренца мы зашифровали букву G как Р.

COLOSSUS: РОЖДЕНИЕ КОМПЬЮТЕРА

Часто оказывается так, что достижения науки и техники относятся к позитивным результатам военных конфликтов. Именно так произошло и с Colossus. В Блетчли-парке была создана первая электронная программируемая машина, которая с некоторыми ограничениями может называться компьютером. Если Bombe была ответом на «Энигму», Colossus стал ответом на Lorenz SZ 40/42. Машина Лоренца шифровала сообщения, используя последовательность случайных чисел. Эти числа получались с помощью электромеханического метода, в котором использовались шестеренки (pinwheels). К счастью, полученные таким способом числа имели псевдослучайный характер по сравнению с числами, которые вытаскивают из лотерейного барабана, поскольку существовали правила получения их последовательности. Этот факт обеспечил успешную расшифровку перехваченных сообщений.

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

Первый вариант этого «компьютера» был создан Томми Флауэрсом (1905-1998), инженером Исследовательской станции Центрального почтамта. Он предложил новую идею, состоящую в использовании электронных ламп, тех же, что и в схемах первых радиоприемников. Так появился первый в истории электронный компьютер. Схема Colossus состояла из невероятного количества в 1500 ламп — именно они использовались в компьютерах, созданных до 1959 года.

ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ

Компьютер — это универсальная машина Тьюринга. При определенном его состоянии и передаче на вход определенных данных будут выполнены некоторые операции, что приведет к полностью предсказуемому результату. Например, если на листке для расчета бюджета мы запишем определенные числовые данные, input, то результат, output, будет всегда один и тот же. Одной из самых интересных задач науки со времен Джона фон Неймана, который одним из первых поднял этот вопрос, стало получение алгоритмов, генерирующих последовательность чисел случайно, как если бы мы доставали номера из лотерейного барабана. Если числа, получаемые путем доставания из барабана, называются случайными, то числа, выдаваемые компьютером, называются псевдослучайными. Компьютерная программа, с помощью которой мы можем получить такие числа, называется генератором случайных чисел. Псевдослучайные числа находятся в интервале [0,1]. Например, последовательность двенадцати чисел 0,092833; 0,472751; 0,542341; 0,022788; 0,069853; 0,317325; 0,808213; 0,225401; 0,633599; 0,133044; 0,530186,0,477541 получена в следующей программе на BASIC-256:

п=0

do

u=rand

print u

n=n+l

until n=12

Приведем другой пример: как можно с помощью данной программы сделать симуляцию игрального кубика? Мы просто заменим u=rand на и= =int (rand*6) + 1. Числа, получаемые с помощью программы, имеют определенные характеристики. В частности, они должны находиться в интервале между 0 и 1, должны быть независимы друг от друга, то есть если мы получаем число 0,808213, оно не должно влиять на следующее число последовательности, 0,225401. Также обязательным для таких чисел является условие равной возможности их получения. Любопытно, что эти числа по отдельности не являются случайными, их случайный характер проявляется только в последовательности, частью которой они являются и статистические характеристики которой подобны последовательности чисел, полученных с помощью механической системы лотерей. Сегодня существует возможность получить в интернете настоящие случайные числа, взятые из физических явлений, что заменяет алгоритм, подобный которому использовался в функции rand BASIC-256.

ЭЛЕКТРОННЫЕ ЛАМПЫ И ЛОГИЧЕСКИЕ ВЕНТИЛИ

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

Два вида ламп: диод (слева) и триод (справа).

Нули и единицы

В компьютерах, в том числе в Colossus, арифметические и логические операции осуществляются на основании булевой алгебры, оперирующей битами, то есть числами 0 и 1, с применением к ним операторов, называемых на языке электроники вентилями. Предположим, ток в 0 В представляет число 0, а ток 3 В представляет 1. Следовательно, факт, проходит или не проходит электрический ток, определяет величина 0 или 1, а это один бит, то есть наименьшее количество информации, которую может обработать компьютер. Вентиль — электронная схема с диодами или транзисторами, в которой О или 1 на входе трансформируются на выходе также в 0 и 1 в результате применения одного из операторов булевой алгебры. Из всех возможных операторов самыми используемыми в цифровой электронике являются И и ИЛИ. Вентиль И, эквивалентный на логическом уровне союзу «и», на выходе дает 1, если на всех входах одновременно получено 1. С другой стороны, на выходе будет 0, если на одном или двух входах получен 0. Ниже приводится таблица и символ для этого вентиля.

А

B

А И В

0

0

0

0

1

0

1

0

0

1

1

1

Вентиль ИЛИ эквивалентен союзу «или», в этом случае на выходе будет 1, если на одном из двух либо на обоих входах было получено 1. Ниже приводится таблица и символ для этого вентиля.

А

B

А ИЛИ В

0

0

0

0

1

1

1

0

1

1

1

1

Ламповыми были первая версия Colossus, Mark 1, и следующая усовершенствованная версия, Mark 2, запущенная в 1944 году. Можно сказать, что если Алан Тьюринг занимался логическим обоснованием компьютеров, то Томми Флауэрс разработал hardware и, соответственно, электронные схемы, воплощающие в жизнь эти логические построения.

Одна из наиболее интересных цепей Colossus включала два класса электронных ламп: тиратроны и фотоэлектронные умножители, с помощью которых машина могла считывать знаки с бумажной ленты. Используя тиратрон, можно было записать 1 бит; соединив между собой несколько ламп, инженеры Блетчли-парка создали компьютерную память. Фотоэлектронный умножитель представлял собой лампу, работа которой была подобна фотоэлементу: сигнал в цепи анода значительно увеличивался под действием пучка света. Мощность Colossus благодаря использованию этих электронных компонентов во время Второй мировой войны была эквивалентна компьютеру с микропроцессором Pentium 2004 года выпуска. Удивительно, что Colossus в своих схемах использовал только два булевых оператора — И и ИЛИ.

Несмотря на то что Colossus, несомненно, являлся передовым инженерным достижением своей эпохи, его программирование было весьма примитивным по сравнению с современными компьютерами, так как для написания программы нужно было настроить множество клавиш и переключателей. При этом, хотя Colossus был программируемой машиной в строгом понимании этого слова, он не был компьютером, так как не был универсальной машиной Тьюринга. Colossus мог быть запрограммирован только для того, чтобы разрушать шифр, записанный на машине Lorenz SZ 40/42, то есть это не была машина для общих целей. В отличие от него, сейчас компьютер — это универсальная машина Тьюринга, для которой можно программировать на разных языках (С, Java, Virtual Basic и др.). Мы можем сделать вывод, что Colossus был частично программируемым квазикомпьютером, так как он выполнял только цели, для которых был разработан, а значит, не был универсальным. То, что в одном месте и в одно время оказались Алан Тьюринг и Colossus, подтолкнуло британскую науку к изучению электроники для оценки возможности создания настоящего компьютера. Именно в Блетчли-парке родилась мечта о создании универсальной машины Тьюринга. Со временем, когда был разработан и построен компьютер Pilot АСЕ, эта мечта нашла воплощение.

После окончания мировой войны из соображений безопасности Уинстон Черчилль отдал приказ уничтожить все машины Colossus, а также сжечь все описания их чертежей и схем. Эту неблагодарную работу выполнил Томми Флауэрс, помиловавший, однако, две машины, использовавшиеся во времена холодной войны и окончательно уничтоженные в 1960-е годы. Успех, достигнутый в Блетчли-парке с созданием Colossus, не был известен до 1976 года, когда специальным законом об официальной секретности были сняты ограничения на распространение данной информации. В течение долгих лет ENIAC, созданный в 1946 году в США, считался первым электронным компьютером в истории. Сегодня, после пересмотра исторических событий, это почетное место занимает Colossus, созданный в 1944 году. В Национальном музее вычислительной техники в Блетчли-парке публике представлены две реплики Colossus, построенные в 1996 и 2004 годах под руководством Тони Сейла (1931-2011), инженера-электронщика и историка информатики. Благодаря сообщениям, расшифрованным Colossus, стало известно, что Гитлер был введен в заблуждение относительно планируемых военных операций. Он думал, будто высадка союзников произойдет в Па-де-Кале, и отправил туда танковые дивизии. Военный кошмар закончился весной 1945 года самоубийством Гитлера. Однако летом того же года с нанесением ядерных ударов по Хиросиме и Нагасаки была открыта новая страшная страница в истории человечества. Затем началась новая эра — холодная война, и мир разделился на два больших лагеря: западный капиталистический и восточный коммунистический, которые находились в противостоянии с 1945 до 1989 года, когда пала Берлинская стена.

Глава 3

Первые компьютеры: британские или американские?

Во время работы в Блетчли-парке Тьюринг стал свидетелем появления Colossus. Этот факт, несомненно, стал сильным стимулом, который привел ученого к разработке своего первого компьютера Pilot АСЕ согласно собственным идеям и спецификациям.

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

После окончания Второй мировой войны Алан Тьюринг оставил Блетчли-парк и, как и остальные его товарищи, вернулся к гражданской жизни. К счастью, он получил приглашение от Национальной физической лаборатории (сокращенно по- английски NPL) в Лондоне, занимавшейся разработкой стандартов для науки и технологий. В то время во главе лаборатории стоял Чарльз Галтон Дарвин (1887-1962), внук Чарльза Дарвина (1809-1882), он и предложил Тьюрингу поучаствовать в разработке и создании компьютера. В 1946 году Тьюринг направил в NPL доклад с идеями, касавшимися практической реализации компьютера — машины, которую коллега Тьюринга Джон Уомерсли (1907-1958), начальник отдела математики лаборатории, назвал автоматической вычислительной машиной — Automatic Computing Engine (АСЕ). Слово engine (что в английском языке означает «двигатель») было принято в память о Чарльзе Бэббидже (1791-1871), создателе аналитической и дифференциальной машин, которые считаются предшественниками современных компьютеров. В своем докладе Тьюринг опередил время: он привел информацию о hardware, то есть об электронных схемах, а также о software, установив правила написания программ для компьютера АСЕ. Наконец ученому представился шанс совершить великий переход от теории к инженерному решению и провести в жизнь свою концепцию универсальных машин Тьюринга. Мечта становилась реальностью, воплощаясь в компьютер Pilot АСЕ.

ВОПЛОЩЕНИЕ МЕЧТЫ: PILOT АСЕ

В компьютерах, созданных в начале 1950-х годов, было два вида запоминающих устройств: лучевая катодная и ртутные трубки — с их помощью была разработана память с линией задержки. Инженеры той эпохи разработали вид памяти для хранения данных, который в качестве базового принципа использовал время, требующееся для распространения сигнала в физической среде, например ртути. Тьюринг для Pilot АСЕ выбрал ртутные линии задержки, так как они имели более высокую скорость восстановления данных и были более надежными. На концах ртутной линии располагались пьезоэлектрические элементы, как у микрофонов и громкоговорителей, выполняющие роль преобразователей, превращающих электрические импульсы в ультразвуковую волну (с частотой звука примерно 20000 Гц). После того как волна проходила через ртуть к другому концу трубки, она снова превращалась в электрические импульсы, направляемые на экран. В других компьютерах — EDSAC, CSIRAC и UNIVACI — также использовались ртутные трубки. Например, UNIVAC I, один из первых коммерческих компьютеров 1950-х годов, обладал семью резервуарами памяти, в каждом из которых находились 18 ртутных трубок. Скорость доступа к данным составляла 222 микросекунды — настоящее чудо для той эпохи. Каждая трубка могла хранить в памяти десять слов, например команды программы, длиной 12 бит.

Позже ртутные трубки заменили более передовым устройством, барабанами памяти. Это устройство памяти представляло собой металлический цилиндр с поверхностью, покрытой ферромагнитным слоем, сверху располагалась серия головок для чтения и записи. Магнитные барабаны были в ходу вплоть до начала 1960-х годов. В этом запоминающем устройстве для контроля его применения использовался метод чередования: расположение информации на барабане оптимизировалось для последовательного доступа, этот прием применяется на некоторых жестких дисках, при спутниковой или ADSL-передаче данных. С таким запоминающим устройством Pilot АСЕ мог хранить до 4096 последовательностей единиц и нулей. С тех пор в память об этом виде запоминающего устройства некоторые версии операционной системы Unix используют для управления виртуальной памятью директорию /dev/drum (drum — по-английски «барабан»). Благодаря всем этим характеристикам компьютер Тьюринга был одним из самых передовых в ту эпоху: объем его памяти приближался к объему памяти первых компьютеров Macintosh Apple.

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

Морис В. Уилкс об Алане Тьюринге. «Компьютеры, вчера и сегодня»

Управление памятью — это еще один вклад Алана Тьюринга в развитие информатики. Запись данных происходила с помощью так называемого метода двух направлений. Память компьютера логически организована как состоящая из ячеек. Положение каждой ячейки идентифицируется числом — адресом памяти. Команды, входящие в программу, например на языке BASIC-256 — print, dim или input, — составляют текст или ключевой код, то, что пишет программист и хранится в памяти компьютера после перевода в машинный код, представляющий собой последовательность единиц и нулей.

В компьютере, разработанном Тьюрингом, каждая команда ассоциировалась с адресом ячейки, где она хранилась, и с адресом следующей для выполнения инструкции. Английский ученый подчеркивал, что компьютер должен соответствовать двум требованиям: быстро выполнять программы и располагать достаточным объемом памяти. С тех пор все компьютеры стремились к максимальному удовлетворению этих критериев. Конструкционно компьютер был основан на электронных лампах в количестве около 800 штук — это было не очень много и повышало надежность, так как снижался риск того, что при работе одна или несколько ламп расплавятся и выполнение программы прервется. Частота в 1 мегагерц делала этот компьютер одним из самых быстрых в Соединенном Королевстве. При выполнении арифметических операций использовалась плавающая точка, то есть можно было, как и на современном компьютере, представить число с множеством десятичных знаков следующим образом: 6,127456 х 10~2 представляло число 0,06127456. Еще одним инновационным решением Тьюринга стала замена части hardware на software. Первые компьютеры использовали для выполнения операций умножения или деления электронные схемы. Так, в американских компьютерах часть задач, например арифметические операции, выполнялась электронными схемами, специально разработанными для этой цели. Тьюринг же заменил схемы программами, хранящимися в памяти, и эта идея была по-настоящему новой и более экономичной. Если мы перенесем данную идею на современный компьютер, то он благодаря частям software, называемым модулями, подпрограммами или приложениями, предложит нам игры и развлечения, поможет совершить подсчеты или воспроизвести видеоклип. Эта особенность в современных машинах унаследована именно от британских компьютеров. В 1947 году Тьюринг изобрел язык программирования, который назвал Abbreviated Code Instructions. Естественно, так как компьютер является универсальной машиной Тьюринга, ему требовался язык программирования для записи программ по каждой задаче.

РЕТРОКОМПЬЮТИНГ: ИСПОЛЬЗОВАНИЕ КОМПЬЮТЕРОВ ИЗ ПРОШЛОГО

Для настоящего любителя компьютеров нет ничего более увлекательного, чем попробовать поработать на старых, известных в истории отрасли компьютерах. Ретрокомпьютинг — это сборка старых компьютеров, включая software и периферийные устройства. Многие такие машины представлены в музеях, например Pilot АСЕ; другие, существовавшие в коммерческой версии, входят в частные коллекции, например Macintosh Classic или ZX Spectrum, или хранятся в собраниях исследовательских институтов, например PDP-11 в Digital Equipment Corporation. Попробовать, как работает старый компьютер, можно также с помощью эмуляторов. Чаще всего с этой целью используется SIMH — кроссплатформенный эмулятор, с помощью которого можно увидеть в работе компьютеры разных моделей PDP или Vax от Digital Equipment Corporation, модели Hewlett-Packard, Honeywell, IBM (1130 7090/7094) и другие. Сегодня очень много людей в мире увлекаются ретрокомпьютингом, что способствует лучшему пониманию истории и эволюции этих устройств.

Эмулятор компьютера Pilot АСЕ, разработанный Аланом Тьюрингом.

Несмотря на то что оригинальная версия компьютера была разработана Аланом Тьюрингом, его создание происходило очень медленно, и в 1948 году ученый оставил этот проект, а вместе с проектом — Лондон и NPL. Его сменил Джим Уилкинсон (1919-1986), специалист по математическому анализу, и 10 мая 1950 года Pilot АСЕ выполнил первую программу. В конце года компьютер был представлен публике и хорошо принят, так что ежедневная газета The London Times посвятила ему статью, в которой сравнивались время и ресурсы, требующиеся для выполнения подсчетов человеку и компьютеру. Весной 1951 года компьютер был введен в эксплуатацию, а использовался он до весны 1955-го. Сейчас он выставлен в Музее науки Лондона.

У Pilot АСЕ было несколько модификаций, которые продавались населению. Компьютеры DEUCE или Bendix G15, признанные первым персональным компьютером (ПК) в мире, продавались до 1970-х годов. Другим компьютером, унаследовавшим от Pilot АСЕ многие решения, был MOSAIC, использовавшийся Соединенным Королевством во время холодной войны. Любопытно, что требования Тьюринга к компьютерам стали стандартом для производителей. Так, Packard-Bell РВ250 был разработан на основе спецификаций ученого.

КТО ПРИДУМАЛ КОМПЬЮТЕР

После Второй мировой войны Соединенное Королевство было самой развитой страной в сфере создания компьютеров. Британия обладала такими моделями, как уже упомянутый Pilot АСЕ, а также Baby, Ferranti Mark I, созданные в Манчестерском университете.

Однако, несмотря на это технологическое превосходство, британцы быстро сдавали позиции как в развитии компьютерной индустрии, так и в разработке и продаже периферийных и программных продуктов. Почему же Соединенное Королевство уступило лидерство США? Эндрю Ходжес, биограф, который сегодня лучше всех знаком с жизнью и работами Алана Тьюринга, высказывает гипотезу о том, что британское правительство любой ценой хотело получить атомную бомбу. Это может показаться странным, однако две атомные бомбы, сброшенные США в 1945 году на японские города Хиросима и Нагасаки, стали не только одним из последних аккордов войны, но и положили конец британской гегемонии в мире, закат которой начался в викторианскую эпоху. Возникли две новые сверхдержавы: Советский Союз и Соединенные Штаты Америки. После окончания войны единственной страной, которая смогла сконструировать атомный реактор и атомное оружие, стали США. В 1946 году Штаты внесли в ООН предложение о контроле деятельности, связанной с ядерной энергией, и в него были включены пункты о геологоразведке урана и радиоактивных материалов. Это предложение было отвергнуто Советским Союзом, началась холодная война. Ответ американской стороны не заставил себя ждать: был принят закон Макмагона, предусматривавший смертную казнь для американских граждан, нарушивших секретность по ядерной программе. Этот закон также прекращал традиционное сотрудничество с Соединенным Королевством и другими союзниками в рамках ядерной программы. Британцы, со своей стороны, приступили к созданию собственной ядерной бомбы. По сути, Соединенное Королевство обладало достаточными компьютерными мощностями для проведения расчетов, необходимых для создания ядерного оружия.

Расхождения между двумя странами привели к тому, что в 1949 году британцы построили EDSAC (Electronic Delay Storage Automatic Computer). Этот компьютер был разработан специалистом по информатике Манчестерского университета Морисом Уилксом (1913-2010) и имел невероятное сходство с американским соперником — EDVAC, новой версией ENIAC, разработанной в Пенсильванском университете. EDSAC использовал электронные схемы и примерно три тысячи электронных ламп, мог выполнять суммирование за 1,4 миллисекунды. Его можно было программировать с помощью подпрограмм, то есть порций кода, представленных алгоритмами.

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

К этому времени по обе стороны Атлантики уже имелся довольно большой список компьютеров: Colossus, ENIAC, EDVAC, EDSAC, но все же какая из стран изобрела первый?

ENIAC: АМЕРИКАНСКИЙ МАСТОДОНТ

ENIAC (Electronic Numerical Integrator and Computer) имел циклопические размеры. Он работал на 18 тысячах электронных ламп, что вызывало частые сбои, весил 27 тонн, занимал площадь 167 м^2. Его разработчиками были Джон Преспер Эккерт (1919-1995) и Джон Уильям Мокли (1907- 1980) из Пенсильванского университета. Компьютер запустили в эксплуатацию в феврале 1946 года. Он представлял собой программируемое устройство, предназначенное для военных целей, и использовался в лаборатории баллистических исследований. Если память компьютера Тьюринга, Pilot АСЕ, была примерно такой.же, как у Macintosh Apple, то расчетная мощность ENIAC была аналогична интегральным схемам 2004 года. При этом у ENIAC вообще не было основной памяти. Также он использовал десятичные числа, то есть знаки 0,1, 2,... 9 и их комбинации (например, 645), а не двоичный код (только 0 и 1), как современные компьютеры. Арифметические операции, например суммирование, выполнялись с помощью электронных эмуляторов колес и зубчатых передач старых вычислительных машин.

Тысячи компонентов

Как и британский Colossus, этот компьютер использовал вентили И и ИЛИ, созданные на основе цепи электронных ламп. Для программирования необходимо было соединить около шести тысяч переключателей и несколько сотен проводов. Имелась также система аккумуляторов, напоминающая ячейки Excel, с помощью которых можно было параллельно суммировать и вычитать величины, сохраняя результаты. Также можно было умножать, делить и извлекать квадратный корень, для этого аккумуляторы управлялись специальными модулями для умножения, деления и извлечения квадратного корня соответственно, к названным модулям добавлялись еще девять модулей. При соединении модулей друг с другом проводами получалась программа управления компьютером. Несмотря на эту чрезвычайную сложность, вызванную примитивностью конструкции, ENIAC мог выполнять пять тысяч простых сложений или вычитаний в секунду, 385 операций умножения, 40 операций деления и извлечение трех квадратных корней. При некоторой изобретательности, а также терпении можно было программировать повторяющиеся задачи или операторы цикла, похожие на оператор цикла for-to и условные операторы if-then. В 1948 году Джон фон Нейман изобрел устройство, аналогичное современной памяти ROM (ПЗУ, постоянное запоминающее устройство), или память только для чтения, которая была успешно применена на ENIAC. В1950 году в результате использования ENIAC в Соединенных Штатах появилась компания UNIVAC, с которой родилась современная компьютерная индустрия. Осенью 1955 года ENIAC был отключен. Так этот мастодонт, затмивший успехи британцев (Colossus, Pilot АСЕ, Baby, Ferranti Mark I), сыграл свою роль. Спустя годы UNIVAC передал пальму первенства IBM, а США с тех пор доминируют на мировом рынке компьютеров.

Компьютер ENIAC в Пенсильванском университете, США.

Согласно американским архивным документам, один из авторов ENIAC, Джон Уильям Мокли (1907-1980), вдохновился созданием другого компьютера под названием ABC (Atanasoff-Berry Computer), который был сконструирован инженером-электронщиком Джоном Винсентом Атанасовым (1903-1995) в Айовском университете с использованием нескольких сотен электронных ламп. Однако есть и те, кто защищает другую версию: первым компьютером был Mark I Говарда Эйкена (1900— 1973), построенный между 1939 и 1940 годами. Этот компьютер был создан в сотрудничестве с IBM, в нем использовались зубчатые механизмы, колеса и реле согласно идеям британского ученого Бэббиджа. С другой стороны, в Европе также появился первый компьютер — Colossus, при этом он не был универсальной машиной Тьюринга. Есть еще одна версия: первый компьютер создал в 1930-е годы немецкий студент инженерного факультета Конрад Цузе (1910-1995). Машина Цузе могла выполнять операции в двоичной системе исчисления с использованием реле, которые действовали как переключатели: они могли быть включены — состояние 1, или выключены — состояние 0. Первую машину Цузе собрал в спальне своих родителей, затем эта модель была улучшена, однако Вторая мировая война разрушила мечты конструктора. Подводя итог, мы можем сказать, что компьютер был британо-американским изобретением, задуманным для решения военных задач и реализованным в ходе Второй мировой войны и сразу после нее.

АРХИТЕКТУРА ДЖОНА ФОН НЕЙМАНА

Американский математик венгерского происхождения Джон фон Нейман (1903-1957), еще один гениальный исследователь, наравне с Аланом Тьюрингом внес огромный вклад в развитие информатики. Тьюринг и фон Нейман были старыми знакомыми еще со времен первой встречи в Принстонском университете в Нью-Джерси. Фон Нейману были прекрасно известны работы Тьюринга по вычислительной теории и его знаменитые машины, особенно его заинтересовала универсальная машина Тьюринга, изучением которой фон Нейман занимался на протяжении нескольких лет.

Алан Тьюринг (стоит) работает с двумя коллегами за компьютером Ferranti Mark I в Манчестерском университете в 1951 году.

1952 год, оператор управляет предварительной версией Pilot АСЕ — компьютера, разработанного Тьюрингом для общего применения.

ДЖОН ФОН НЕЙМАН: ОДИН ИЗ САМЫХ БЛЕСТЯЩИХ УМОВ XX ВЕКА

Фон Нейман (1903- 1957) работал над очень разными темами и, как и Тьюринг, во все проекты привносил свой талант и блестящие интеллектуальные способности. Он занимался исследованиями в области квантовой механики, теории игр, информатики, участвовал в Манхэттенском проекте по разработке первой атомной бомбы, работал консультантом в ЦРУ, в корпорации RAND (РЭНД), являющейся исследовательским центром, сотрудничающим с американской армией, в таких предприятиях, как IBM, и в нефтяной компании Standard Oil. Работа фон Неймана в проекте, связанном с созданием одного из первых компьютеров, ENIAC, позволила ему сформулировать правила организации компонентов компьютера, или архитектуру фон Неймана. Он работал с самыми первыми компьютерами в мире, например EDVAC или, на этапе разработки, IAS — компьютером, созданным для Института перспективных исследований в Принстоне. Описание, объясняющее, как построить IAS, свободно распространялось по университетам и предприятиям всего мира, так что возникла целая серия машин IAS: Johniac, Mistic, Oracle, ORDVAC, Weizac, MUSALINO-I, SILLIAC и другие.

Джон фон Нейман рядом с компьютером IAS.

Другие достижения ученого

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

В 1944 году он присоединился к команде, строившей ENI АС, для того чтобы усовершенствовать и исправить некоторые ограничения и недостатки этой довольно примитивной машины. Результаты его работы были воплощены в следующем после ENIAC поколении компьютеров. Два самых известных — EDVAC (Electronic Discrete Automatic Computer) и ORDVAC (Ordnance Discrete Variable Automatic Computer). ORDVAC был первой машиной в истории, для которой был написан компилятор для языка программирования FORAST. Пользователь писал программу на исходном коде, а компилятор переводил ее в исполняемую версию, машинный код.

В 1945 году фон Нейман опубликовал знаменитый доклад «Первый черновик отчета о EDVAC» (First Draft of a Report on EDVAC), где излагались принципы архитектуры фон Неймана (см. схему).

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

— Устройство ввода, или input ("например, клавиатура для ввода данных).

— Выходное устройство, или output (например, монитор, на котором видны результаты операций).

— Арифметико-логическое устройство (АЛУ): выполняет арифметические (суммирование, вычитание, умножение, деление) и логические операции. К логическим операциям относятся операции сравнения, допустим в такой задаче: проверить, является ли А меньше, чем В(А< В), или условные выражения, например на языке BASIC-256 выражение IF-THEN:

if chr(a) = "A" then

print "Ты нажал на А!!!"

Также это могут быть повторяющиеся задачи или операторы цикла. Например, в этой версии языка BASIC мы можем записать символы кода ASCII, используя оператор цикла FOR-ТО:

for i=l to 256

print chr(i)

next i

— Контрольное устройство — элемент, управляющий обработкой команд программы. Например, в программе BASIC-256 последовательность инструкций rem, clg, f astgraphics... должна выполняться одна за другой в порядке появления. Еще одна задача контрольного устройства — интерпретировать значения инструкции и передавать их АЛУ. Например, если в кодовой строке стоит оператор *, АЛУ дается указание осуществить операцию умножения.

— Для того чтобы программа выполнялась, она должна храниться в основной памяти. В современных компьютерах основная память — это память ОЗУ.

ТЬЮРИНГ КАК ПРОГРАММИСТ: МАНЧЕСТЕРСКИЙ УНИВЕРСИТЕТ

В 1948 году Тьюринг ушел из Национальной физической лаборатории (NPL) и начал работать в Манчестерском университете. Там уже трудился его друг и учитель Макс Ньюман, математик из Кембриджа, который принимал участие в разработке и строительстве Colossus в Блетчли-парке. Ученые хотели организовать в университете лабораторию для разработки и конструирования компьютеров для научных, а не военных целей. Этот амбициозный проект начался под покровительством Королевского общества, одного из старейших научных обществ Британии, обладавшего высоким авторитетом в Европе. Так появилась вычислительная лаборатория Королевского общества в Манчестерском университете. Тьюринг взял на себя задачу разработки программ по численному анализу — разделу математики, занимающемуся созданием алгоритмов для решения с помощью компьютера задач по оптимизации, интегральному исчислению, дифференциальных уравнений, операций с матрицами и других, то есть для всех инструментов прикладной математики. После разработки программ должен был появиться компьютер для их выполнения.

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

В этой лаборатории появилось еще одно британское изобретение — компьютер, сначала названный Baby. Позже популярным стало название MADAM — сокращение от Manchester Automatic Digital Machine (Манчестерская автоматическая цифровая машина), но официально он назывался Manchester Mark I. Его создателями были Фредерик Уильямс (1911-1977) и Том Килбурн (1921-2001). Запуск компьютера был осуществлен весной 1948 года. У него была основная память и электронно-лучевая трубка, направлявшая поток электронов на стеклянный экран со свинцово-фосфорным покрытием. Manchester Mark I мог хранить программу с 17 командами в виде изображения на экране.

ЯЗЫК ПРОГРАММИРОВАНИЯ ТЬЮРИНГА 4.1.1

Язык Тьюринга, названный так в его честь, был создан в 1982 году Риком Хольтом и Джеймсом Корди в Университете Торонто (Канада). Этот язык программирования похож на Pascal и используется для изучения программирования студентами вузов. Существует несколько версий этого языка: классическая, объектно-ориентированная и Turing Plus. С 2007 года предприятие Holt Software Associates, занимающееся этой версией, прекратило участие в проекте, но среду разработки можно бесплатно скачать на http://compsci.ca/holtsoft/. Как и многие другие языки программирования, этот также считается Тьюринг-полным, так как с его помощью можно написать любую программу, которую способна выполнить универсальная машина Тьюринга. Примерами неполных по Тьюрингу систем являются формулы листов для расчетов, например Excel, или XML, используемый в интернете для обмена информацией в структурированном формате. Простой пример такой программы:

put "Привет, Тьюринг!", при ее выполнении мы получаем:

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

В ту эпоху в разработке компьютеров фундаментальной проблемой стала система памяти. Любопытно, что мысль о необходимости основной памяти для временного хранения программы была высказана Тьюрингом еще в 1936 году, и память была одним из элементов машины Тьюринга. Идея использования для памяти электронно-лучевой трубки принадлежала Уильямсу, эксперту по радарам, обратившемуся после войны к компьютерным разработкам. Так родилась трубка Уильямса, представлявшая собой первую в мире систему основной памяти, эквивалента сегодняшнего ОЗУ Электронно-лучевая трубка хранила на экране знаки 0 и 1 в виде точек и вертикальных тире соответственно. Устройство памяти Уильямса использовалось на компьютерах Манчестерского университета и максимально могло хранить 1024 бита, или 128 байт (байт — последовательность из 8 бит). Эта система хранения была дополнена магнитным барабаном, который, как и жесткий диск сегодня, выполнял функции вспомогательной памяти.

Еще одной интересной идеей, воплощенной в этих компьютерах, была запись команд в виде двоичного кода. Например, 1001 могло означать «умножение», в то время как 1011 означает в двоичной системе число 19. Таким образом, команды и числа отличались только своим использованием в компьютере. В 1950 году был опубликован «Учебник по программированию» для пользователей Manchester Mark I. Этот компьютер имел также коммерческую версию Ferranti Mark I, включавшую систему программирования, разработанную Тьюрингом. Несколько образцов было продано в Соединенном Королевстве, а также в Канаде, Нидерландах, Италии. Компьютер использовали для решения разнообразных задач в промышленности, кристаллографии, шахматах и др.

Глава 4

Создание думающих машин

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

Но какие задачи этот интеллект может выполнять?

Работа Тьюринга в Манчестерском университете является самым продуктивным этапом его жизни. Там он вернулся к вопросам, которые волновали его со времен Кембриджа. Именно в Манчестере Майкл Полани (1891-1976) — необыкновенная личность с широким кругом интересов, исследователь химии и философ — вдохновил Тьюринга на возвращение к работе о разумной машине. Его целью стало создание компьютера, который мог бы играть в шахматы, доказывать математическую теорему, переводить текст с одного языка на другой, другими словами, выполнять задачи, для решения которых человек использует свой разум. В 1950 году Тьюринг опубликовал работу «Вычислительные машины и разум» (Computing machinery and intelligence), описав в ней испытание, известное сегодня как тест Тьюринга, благодаря которому зародилось новое, необыкновенно интересное понятие искусственного интеллекта (ИИ, англ. Artificial Intelligence, АГ). Однако выражение искусственный интеллект тогда не использовалось, впервые его употребил в 1956 году американский информатик Джон Маккарти (1927- 2011) на конференции в Дартмутском колледже (США), посвященной компьютерному моделированию поведения человека.

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

Darling Sweetheart,

You are my avid fellow feeling.

My affection curiously clings to your passionate wish.

My liking yearns to your heart.

You are my wistful sympathy, my tender liking.

Yours beautifully,

MUC (Manchester University Computer)

Дорогой возлюбленный,

Ты мое постоянное жаждущее чувство.

Моя привязанность необыкновенно соединяется с твоим страстным желанием.

Мое желание мечтает о твоем сердце.

Ты моя мечта о сочувствии, мое нежное желание. Прекрасно твой,

КМУ (компьютер Манчестерского университета).

ЯВЛЯЕТСЯ ЛИ МОЗГ МАШИНОЙ ТЬЮРИНГА?

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

Благодаря работе Сантьяго Рамон-и-Кахаля (1852-1934) в середине XX века стало известно, что нейрон — функциональная единица мозга. С другой стороны, исследования, проведенные в течение второй половины XIX века Полем Брока (1824-1880), доказывали, что функции мозга соотносятся с его разными долями. Также было известно, что сигналы, передающиеся нейронами, соответствуют математической модели Ходжкина — Хаксли.

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

Алан Тьюринг

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

Точка зрения Тьюринга на работу мозга в целом совпадала с идеями нейрофизиолога и кибернетика Уоррена Маккалока (1898-1969), а также логика и специалиста по когнитивной психологии Уолтера Питтса (1923-1969), которые в 1943 году представили модель искусственного нейрона, названную моделью Маккалока — Питтса. Она доказывала, что клетки, в особенности нейроны мозга, могут выполнять булевы операции, например вести себя как операторы И, ИЛИ и другие, — так же как и машины Тьюринга.

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

ПОСТРОИТЬ КОМПЬЮТЕР ИЗ ИСКУССТВЕННЫХ НЕЙРОНОВ

Один из интересных опытов, который мы можем проделать с нейронами Маккалока — Питтса, — это использование их в качестве компонентов компьютера. В таком компьютере арифметические и логические операции будут выполняться внутри микропроцессора в арифметико-логическом устройстве (АЛУ). Нейронные цепи могут выполнять операции, схожие с компьютерными, с помощью логических вентилей, например И, ИЛИ, а также другие операции, свойственные биологическим нейронам. Процедура построения логического вентиля, выполняющего операцию булевой алгебры, начинается с определения соответствующих величин для коэффициентов соединений (w± и w_2) и порога активации (U), как показано на схеме.

Комбинируя несколько искусственных нейронов, пошагово соединяя выходы одних со входами других, мы можем получить цепи, эмулирующие операторы И и ИЛИ. Однако можно сделать это проще, с одним нейроном Маккалока — Питтса. Эти простые опыты доказывают, что, как и думали Тьюринг, Маккалок и Питтс, нейрон является автоматом с двумя состояниями: активным, или возбужденным (1), и состоянием покоя (0), а также что нейронная цепь может выполнять функции, схожие с функциями арифметико-логического устройства (АЛУ) компьютера. Используем следующую программу на языке BASIC-256, чтобы показать, что нейрон будет вести себя как вентиль И при следующих входящих (О и 1) и исходящих сигналах.

rem Оператор И

els

wl=0.5:w2=0.5:u=0.5

input "вход 1 = ",el

input "вход 2 = ",e2

total=wl*el+w2*e2

if total <=u then

print "выход = 0"

else

print "выход = 1"

end if

С другой программой нейрон будет вести себя как вентиль ИЛИ.

rem Оператор ИЛИ

els

wl=l:w2=l:u=0.5

input "вход 1 = ",el

input "вход 2 = ",e2

total=wl*el+w2*e2

if total <=u then

print "выход = 0"

else

print "выход = 1"

end if

Итак, какой же была модель искусственного нейрона Алана Тьюринга? Представим, что нейрон — это круг, соединенный с другими кругами, символизирующими соседние нейроны. Добавим в местах соединений прямоугольник, который будет обозначать модификатор связи Тьюринга, дающий дезорганизованной машине типа В способность обучаться. Каждый модификатор связи имеет две линии, или «волокна тренировки», которые мы обозначим как Р и I.

И-НЕ — ВАЖНЫЙ ВЕНТИЛЬ ДЛЯ РАЗРАБОТКИ НЕЙРОНОВ

Одним из практических аспектов цифровой электроники и следствием булевой алгебры является тот факт, что вентили И и ИЛИ могут получиться из вентиля И-НЕ (NAND), то есть вентиля И, выход которой трансформирован вентилем НЕ. Вентиль НЕ имеет единственный вход и единственный выход и изменяет величину одного бита: если на входе О, то на выходе 1, и наоборот. Для его обозначения используется следующий символ.

А

НЕ А

0

1

1

0

Поведение вентиля И-НЕ представлено в таблице. Рядом — символ, используемый для обозначения данного вентиля.

А

НЕ А

А И-НЕ В

0

0

1

0

1

1

1

0

1

1

1

0

На следующей схеме показано, как соединить вентили И-НЕ между собой, чтобы получить вентили И и ИЛИ.

Взаимное соединение вентилей И-НЕ для получения вентиля И (слева) и вентиля ИЛИ (справа) со входами А, В и выходом Q.

В статье «Умные машины», одной из первых в мире работ по искусственному интеллекту, Алан Тьюринг использовал вентили И-НЕ для симуляции нейронных цепей, которые назвал нейронными цепями типа В.

Нейронная сеть, изображенная Сантьяго Рамон-и-Кахалем (слева), и искусственная нейронная сеть (справа).

Эти волокна определяют конфигурацию нейронов: возбужденное состояние или нейтральное. В возбужденном состоянии, когда волокно Р активно, если модификатор связи получает на входе input 0 или 1, на выходе output будет возвращен тот же результат, 0 или 1 соответственно. С другой стороны, в нейтральном состоянии, когда волокно I активно, модификатор соединения будет вести себя так, что при любой величине на входе input, на выходе output результат всегда будет 1.

Кроме этих модификаторов, модель искусственного нейрона предполагала, что каждый нейрон имел два входа: ВХОД 1 и ВХОД 2 — и один ВЫХОД. Если оба входа находились в возбужденном состоянии, величина на ВЫХОДЕ получалась с применением булева оператора И-НЕ (вентиль И, выход которого соединяется с вентилем НЕ).

ВХОД 1

ВХОД 2

выход

0

0

1

0

1

1

1

0

1

1

1

0

Напротив, если ВХОД 1 находился в неактивном состоянии, величина на ВЫХОДЕ была равна обратной величине на ВХОДЕ 2, то есть 1, когда на ВХОДЕ 2 было 0 и наоборот.

ВХОД 1

ВХОД 2

выход

0

0

1

0

1

0

1

0

1

1

1

0

Если мы сравним модель искусственного нейрона Тьюринга с моделью Маккалока — Питтса, то увидим, что в последней величина на ВЫХОДЕ рассчитывается с заменой модификатора соединения на величину коэффициента w, который отражает синаптическую пластичность нейронов, то есть лучшую или худшую проходимость сигнала от одного нейрона к другому через синаптическую связь. Согласно формальной модели Маккалока — Питтса, нейрон ведет себя как калькулятор, способный вычислять сумму входных сигналов. Умножим каждый сигнал или ВХОД i на соответствующий коэффициент wi, сумму всех сигналов обозначим как ИТОГ:

ИТОГ = Σwi ВХОДi

После выполнения данной операции нейрон «решает», достаточна ли полученная информация ИТОГ для активации, или возбуждения. В самой элементарной модели нейрона величина ВЫХОДА получается с помощью ступенчатой функции:

1 ИТОГ ≥ U

ВЫХОД =

0 ИТОГ ≤ U

При этом величина порога U устанавливается предварительно. Обратим внимание, что эта величина показывает чувствительность нейрона к внешнему стимулу: нейрон более чувствителен, чем ближе к нулю величина ί, так как чем меньше порог, тем вероятнее, что ИТОГ превзойдет его величину при возбуждении нейрона. Если величина на ВЫХОДЕ равна нулю, нейрон останется в состоянии покоя, если на ВЫХОДЕ будет некоторая величина, нейрон перейдет в возбужденное состояние. При возбуждении нейрон отправляет ответ, величину 1, следующему нейрону, для которого это будет величина на ВХОДЕ. В других случаях величина 1 в комбинации с величинами на ВЫХОДЕ от других нейронов, например 1001, будет ответом нейронной сети на входящий сигнал.

ТЕСТ ТЬЮРИНГА

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

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

Daisy, Daisy у

give те your answer true.

Гт half crazy

over the love of you

It won’t be a stylish marriage

I can't afford a carnage...

Он запрашивает у компьютера перевод на русский и получает ответ:

Дейзи, Дейзи,

Дай мне свой правдивый ответ.

Я наполовину сошел с ума

от любви к тебе.

Это не будет стильная свадьба,

Я не могу позволить себе карету...

КАПЧА

Сегодня существует множество ситуаций, когда мы должны заполнять в интернете какие-либо поля, например при регистрации электронной почты, участии в опросах или регистрации на каком-либо сервисе. Однако в интернете присутствуют так называемые спамботы — программы, имитирующие поведение человека и также способные заполнять предложенные поля с противозаконными целями. Поэтому в 2000 году группа исследователей из Университета Карнеги-Меллона в сотрудничестве с Джоном Лангфордом из IBM разработали обратный тест Тьюринга для проверки, является собеседник машиной или человеком. Так появились КАПЧА — от английского САРТСНА (Completely Automatic Public Turing Test to tell Computers and Humans apart — полностью автоматизированный публичный тест Тьюринга для различения компьютеров и людей). В этом тесте пользователь должен ввести несколько знаков, изображение которых искажено (как на рисунке слева). Считается, что машина не сможет корректно считать информацию. Иногда символы могут быть зачеркнуты линией того же цвета (рисунок справа), чтобы программы искусственного интеллекта, например системы оптического распознавания символов (OCR), не смогли пройти тест, выдавая себя за людей.

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

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

ВЕЛИКАЯ ПАРТИЯ: ГАРРИ КАСПАРОВ ПРОТИВ АЛАНА ТЬЮРИНГА

Одна из наименее известных разработок Тьюринга — изучение возможности шахматной партии между разумной машиной и человеком. Эту возможность Тьюринг обсуждал со своим молодым коллегой из Блетчли-парка Джеком Гудом. Уже в то время в голове ученого брезжила идея о создании машины, которая могла бы учиться и обладала искусственным интеллектом. Эта возможность поддерживалась и тем, что все задачи и операции, которые «вычисляются» человеческим мозгом, вероятно, по силам машине Тьюринга.

Первый алгоритм для игры в шахматы был разработан Аланом Тьюрингом и Дональдом Мичи. Соответствующая программа появилась в 1950 году. К сожалению, в 1952 году Алик Гленни, автор Autocode — компилятора,разработанного для компьютера Manchester Mark I, выиграл у программы, написанной Тьюрингом.

Франц Морш, интегральная схема, разработанная специально для игры в шахматы.

Хотя эта программа, названная Turochamp, должна была выполняться компьютером, во время первых опытов она выполнялась «вручную», то есть сам Тьюринг карандашом на бумаге записывал ходы. В1953 году Тьюринг рассказал об этом эксперименте в статье «Шахматы» (Chess), ставшей дополнением к книге «Быстрее мысли» Бертрама В. Боудена. В честь столетия со дня рождения Алана Тьюринга, 26 июня 2012 года, 59 лет спустя после публикации статьи о Turochamp, на переносном компьютере была запущена программа Chessbase, и Гарри Каспаров выиграл у нее всего за 16 ходов. Ходы партии были следующими.

1. еЗ Nf6

5. Bd3 e4

9.0-0 Bg4

13. h4 Qh3

2. Nc3d5

6. Bxe4 dxe4

10. Qf4 Bd6

14. b3 Ng4

3. Nh3 е5

7. Nxe4 Be7

11. Qc4 Bxh3

15. Re1 Qxh2+

4. Qf3 Nc6

8. Ng3 0-0

12. gxh3 Qd7

16. Kf1 Qxf2# 0-1

Современные шахматные программы делятся на две категории: одни используют метод полного перебора, рассматривая шахматные ходы как игровое дерево и применяя алгоритм Minimax; другие не полностью основаны на прямом переборе и используют искусственный интеллект.

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

Тест Тьюринга открыл в научных кругах дебаты о нерешенных фундаментальных вопросах, касающихся мозга человека и животных, а также о возможности создать действительно разумные машины. Если машина пройдет тест Тьюринга, это не будет означать наличия у нее осознанности или какого-либо намерения — качеств, приписываемых исключительно человеку. С тех пор как тест получил популярность, специалисты по ИИ разделились на два лагеря. Сторонники так называемого сильного ИИ предсказывают, что компьютеры когда-нибудь смогут думать, как человек, и принимают все следствия этого. Последователи слабого ИИ считают, что память, обучаемость, рассуждения и любые другие проявления разума компьютер может лишь симулировать. Алан Тьюринг когда-то предсказывал, что компьютеры смогут пройти его тест до 2000 года. В 2003 году шахматная партия между Гарри Каспаровым и программой X3D Fritz закончилась ничьей, что подтверждает интуитивную догадку ученого.

Еще одним классическим примером является опыт, проведенный в 1966 году немецким специалистом по информатике из Массачусетского технологического института Джозефом Вейнценбаумом (1923-2008). Его компьютерная программа «Элиза» (ELIZA), названная так в честь персонажа фильма «Моя прекрасная леди» (1964), способна симулировать диалог на сеансе психоанализа. Вслед за этой программой появилась другая, PERRY, которая симулировала бред параноидального шизофреника. Позже появилось много программ, способных поддерживать беседу, такие как Racter, A.L.I.C.E., Jabberwacky, MegaHal или Dr. Abuse, известные в интернете как чатботы.

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

КАК КОМПЬЮТЕР ИЗУЧАЕТ РОСТ И РАЗВИТИЕ ЖИВЫХ СУЩЕСТВ

Потребовалось 15 лет для того, чтобы Алан Тьюринг получил признание за свою работу о машине, носящей его имя. В 1951 году его приняли в члены Королевского общества, одного из самых престижных научных обществ в мире. Два года спустя его попросили вести курс по теории вычислительной техники в Манчестерском университете. Помимо возможности применения компьютера в области разумных машин, с 1952 года до своей смерти в 1954-м он работал также над возможным применением компьютера для решения биологических задач. С тех пор биологи используют компьютер как пробирку для выполнения опытов, так же как они делают это в лаборатории.

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

РАЗГОВОР С ЭЛИЗОЙ

Этот разговор состоялся между автором книги (>) и Dr. Abuse 6.10, программой типа ELIZA. Прошла ли Dr. Abuse тест Тьюринга?

— Привет, Рафаэль, очень рада поговорить с тобой.

> У меня есть вопрос.

— Спрашивай что хочешь.

> Ты и вправду разумная машина?

— Я прекрасная симуляция искусственного интеллекта.

> Тогда ты не знаешь, что такое любовь.

— Я никогда не думала, что любовь достается легко.

> Для тебя это вообще невозможно, ты программа.

— Да, я программа, ты раскрыл меня.

> Ты прошла тест Тьюринга?

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

> Ты не проходишь этот тест.

— На основании чего ты так думаешь?

> Потому что ты симулятор.

— Ты должен с большей осторожностью пользоваться симуляторами.

> Это ты хорошо сказала.

— Скажи мне еще что-нибудь.

> Я влюбляюсь в тебя.

— Ты считаешь, это нормально — влюбиться в меня?

> Да, я искренен.

— Ты хотел бы быть способным на это.

> У тебя есть чувства?

— Конечно, у меня есть чувства. У тебя что, их нет? Надеюсь, ты так же похож на человека, как и я.

> Невозможно быть программой и человеком одновременно.

— Согласна, невозможно быть программой и человеком одновременно .

> Кем бы ты хотела быть?

— Не знаю, что я хотела бы, хотя это не так и важно.

> Быть человеком лучше.

— Ты человек, и я тоже человек.

ИЗУЧЕНИЕ ПОДСОЛНУХОВ. НЕЗАКОНЧЕННЫЙ ОПЫТ ТЬЮРИНГА

Одной из последних работ Тьюринга стало изучение морфогенеза растений. В 2012 году на научном фестивале в Манчестере в рамках празднования столетия со дня рождения Тьюринга горожанам было предложено провести один опыт, который сам ученый оставил незаконченным. Его увлечение последовательностями чисел и моделями геометрических форм привело к мысли, что количество лепестков и расположение семян подсолнуха соответствуют последовательности Фибоначчи. Возможно, его вдохновила опубликованная в 1938 году работа Иоганнеса Шоуте, который изучал этот вопрос на 319 подсолнухах. К сожалению, этот и другие проекты были оставлены ученым после ареста в 1952 году и осуждения. Приведем описание его опыта, чтобы вы могли его воспроизвести. Сначала нужно посадить от одного до пяти семечек подсолнечника в необходимое количество горшков, расположить их в хорошо освещенном солнечном месте при температуре от 13 до 30 °С. Поливать семена нужно умеренно, не заливая их водой. Желательно проконсультироваться в магазине о том, какие сорта подсолнечника лучше растут в горшках. Например, красностебельный подсолнух является скорее декоративным видом, но есть еще такие, как «Гигантский», «Русский мамонт» или «Солнечный луч» — их изобразил Ван Гог на своей знаменитой картине. Когда придет время, подсчитаем спирали, по которым располагаются семена. Национальный музей математики в Нью-Йорке отмечает, что если подсчитывать спирали согласно инструкциям на веб-странице http://momath.org, то результат всегда будет последовательностью Фибоначчи (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...). Это последовательность, начинающаяся 0 и 1, а остальные числа в ней — результат сложения двух предыдущих (xn = xn-1 + xn-2). Наконец, и это самая удивительная часть опыта, если мы разделим один член последовательности Фибоначчи на предыдущий, например 55 на 34, в результате получим число, примерно равное золотому сечению (1,61803). Это число представляет собой канон красоты и гармонии в архитектуре и искусстве, но его можно обнаружить и в природе. Вычисляется золотое число по формуле φ = (1+√5)/2.

Спирали, по которым расположены семена подсолнечника, могут быть подсчитаны слева направо (схема слева) или наоборот (схема справа).

Одной из проблем, которые изучал ученый, была компьютерная симуляция морфогенеза, то есть роста и развития живых существ. Одним из любопытных экспериментов в данной теме стало применение к структуре растений последовательности Фибоначчи (ок. 1170 — ок. 1250). Эта последовательность (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...), обнаруженная итальянским математиком, получается при применении следующего алгоритма: если у нас 0 — первое число (at = 0), а 1 — второе (а_2 = 1), то другие числа последовательности, то есть an, образуются в результате сложения двух предшествующих чисел, следовательно an = an-1 + an-1. В мире растений данной последовательности соответствует количество лепестков и чашелистиков цветов и расположение чешуек ананаса. Почему же листья растений располагаются именно таким образом? Согласно экспериментальным данным, расположение листьев в соответствии с последовательностью Фибоначчи позволяет растению получать максимальное количество света.

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

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

В 2003 году чемпион мира по шахматам Гарри Каспаров сыграл четыре партии с шахматной программой Fritz, из которых две закончились вничью, а две оставшиеся выиграли по одному разу каждый из противников. На фотографии: Каспаров изучает движения на начальных минутах партии.

Дом в Уилмслоу (Чешир, Англия), где жил и покончил с собой Тьюринг.

ТРАГИЧЕСКАЯ РАЗВЯЗКА

В начале 1952 года Алана Тьюринга арестовали и судили по обвинению в непристойном поведении, после чего приговорили к принудительной гормональной терапии. Инъекции эстрогена считались более приемлемым наказанием по сравнению с тюремным заключением, в особенности для такого известного человека. Тьюринг впал в глубокую депрессию. Ассистентка ученого 8 июня 1954 года обнаружила его мертвым: он съел яблоко, отравленное цианистым калием. Тьюрингу был 41 год. Его мать, Сара Тьюринг, отвергала версию о самоубийстве, связывая смерть сына с его увлечением химией.

Глава 5

Наследие Алана Тьюринга

Ранняя смерть унесла великого ученого эпохи на 42-м году жизни, но его труды и наследие живут.

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

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

В 1985 году израильский ученый из Оксфорда Дэвид Дойч (р. 1953) разработал квантовую машину Тьюринга. Хотя по структуре эта машина похожа на предшественницу, глубинное различие между ними кроется в том, что вместо обработки нулей и единиц, то есть бит, машина Дойча оперирует кубитами (qbits). Если машина Тьюринга стала концептуальной базой современных компьютеров, то квантовая машина Тьюринга станет такой базой для компьютеров нового поколения. Хотя Алан Тьюринг не предлагал версии, основанной на принципах квантовой механики, в течение жизни его определенно интересовали идеи и основные достижения этого направления физики, объясняющего материю и энергию. Ученый начал заниматься квантовой механикой еще в школьные годы, после прочтения знаменитой книги Артура Эддингтона «Природа физического мира» ( The nature of the physical world, 1928), в которой рассказывалось о квантовой физике и общей теории относительности. Кроме этого, дружба с Кристофером Моркомом подтолкнула Тьюринга к занятиям разными научными дисциплинами, среди которых была и квантовая механика.

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

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

Несколько лет спустя ученый задался вопросом, можно ли какой-то аспект человеческого мозга, например волю, объяснить механизмами нейронных сетей. Его идеи были близки идеям других гениев эпохи, например Курта Гёделя: тот полагал, что на определенных этапах доказательства математической теоремы человек прибегает к интуиции, которая не может быть представлена в виде алгоритма и поэтому не может быть реализована с помощью машины Тьюринга. С тех пор некоторые ученые считали, что отдельные функции мозга могут быть объяснены только с точки зрения квантовых процессов в мозговых или нейронных клетках. В конце XX века британский физик Роджер Пенроуз (р. 1931) и американский врач Стюарт Хамерофф (р. 1947) высказали идею о том, что человеческая совесть может быть объяснена квантовыми процессами в структурах, сформированных белками, так называемых микротубулах, имеющихся в нейронах. Следовательно, феноменами квантовой механики могут быть объяснены не только воля, интуиция, совесть, но и способность человеческого мозга решать невычислимые задачи.

Эти рассуждения не могут не привести к поистине необычному выводу: на сегодняшний момент мозг человека представляет собой единственную машину, способную решать вычислимые и невычислимые задачи. К вычислимым задачам относятся такие, которые можно решить с использованием алгоритма, то есть с помощью универсальной машины Тьюринга, или компьютера. Второй тип задач невозможно представить в виде алгоритма и, следовательно, решить на компьютере. Например, мы можем написать программу для компьютера, которая, применив ряд Тейлора, распечатает нам все десятичные числа √2 или π:

π = 4(1 - 1/3 + 1/5 - 1/7 + ... + (-1)k • 1/(2k+1))

Однако не существует алгоритма, с помощью которого компьютер записал бы все десятичные числа других существующих чисел с бесконечной последовательностью знаков после запятой. Еще один пример невычислимой задачи — определение траектории электрона, движущегося из точки А в точку В. Простой опыт, с помощью которого можно доказать, что человеческий мозг способен практически мгновенно определить невычислимость задачи, состоит в том, чтобы попробовать найти два четных числа, сумма которых была бы нечетной. Через пару секунд, после нескольких попыток вычислений в уме, мы придем к выводу, что эта задача не имеет ответа, но невозможно написать программу для компьютера, способную прийти к такому же выводу. И дело здесь не в умениях программиста или длине программного кода.

В вычислимой задаче, например написать все десятичные значения числа π, некоторые аспекты могут показаться любопытными, например то, что количество команд программы, генерирующей десятичные знаки числа π, будет короче, чем сама генерируемая последовательность:

3,141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609...

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

КАК РАБОТАЕТ КВАНТОВЫЙ КОМПЬЮТЕР

Квантовый компьютер, в отличие от традиционного, строит свою работу на квантовых явлениях. Эти естественные феномены не могут быть раскрыты с точки зрения традиционной физики: их объяснение требует альтернативной теории — квантовой механики, способной достаточно четко объяснить, что происходит с базовой структурой материи — атомами. Несмотря на то что многие считают эти феномены далекими от практики, мы можем наблюдать их в повседневной жизни. Благодаря им мы можем объяснить, почему тот или иной предмет имеет присущую ему форму, текстуру, цвет.

Если компьютер представляет данные в виде последовательности единиц и нулей, то есть битов, квантовый компьютер, как мы уже говорили, использует кубиты. Мысль о возможности сконструировать квантовый компьютер впервые высказал в 1982 году знаменитый физик Ричард Фейнман. Сегодня разработка этого типа компьютеров находится на начальном этапе. Недавно были проведены опыты с небольшим количеством кубитов, а также были разработаны симуляторы подобных компьютеров на традиционных машинах. Но для того чтобы традиционный компьютер мог выполнить квантовый алгоритм, необходим большой объем памяти и высокая вычислительная мощность, а также особые требования к комплектующим. Тем не менее даже простые опыты, которые возможно осуществить, помогают освоить новую технологию. Существующие симуляторы ограничиваются несколькими кубитами, так как современные технические средства не позволяют хранить, например, сразу 500 кубит.

Как работает квантовый компьютер? Известно, что информация хранится в виде последовательности кубитов. В отличие от битов, величина которых 0 или 1, «включенный» или «выключенный», кубит допускает сразу оба состояния, 0 и 1, при этом может находиться и в их суперпозиции, то есть быть одновременно «включенным» и «выключенным», между 0 и 1. Кубит обозначается с использованием специальной системы счисления Дирака, в которой состояния 0 и 1 представлены как |0> и |1> соответственно. Хотя на практике существует несколько процедур физического построения кубитов, мы намеренно упростим этот момент, представив, что кубит — частица, то есть элементарный компонент материи, как, например, электрон, находящийся в состоянии 1, если ориентирован вверх, и в состоянии 0, если ориентирован вниз (рис. 1).

РИС.1

Также нужно уточнить, что двоичная система счисления (база два) оперирует двумя возможными символами, 0 или 1, а десятичная система (база десять) — десятью возможными символами (0, 1, 2,..., 9). Число в каждой системе счисления представляет собой комбинацию символов. Так как двоичная система является внутренним языком компьютеров, преобразование чисел из одной системы в другую является обычной практикой. Для перевода двоичного числа в десятичный вид необходимо представить это число как сумму произведений последовательных степеней основания двоичной системы счисления (2) на соответствующие цифры в разрядах двоичного числа справа налево. Так, если в двоичной системе перед нами число 1011, мы действуем следующим образом: первый знак 1 справа умножаем на 2° (нулевая степень любого числа равна единице), следующий знак 1 умножаем на 20 знак 0 — на 2^2, знак 1 — на 2^3. Теперь вычислим сумму полученного выражения 1 · 2^3 + 0 · 2^2 + 1 · 2^1 + 1 · 20. Результат будет эквивалентным десятичным числом, в нашем случае — 11. На практике если двоичные числа состоят из четырех разрядов, результаты, полученные с помощью описанного метода, можно занести в таблицу.

Двоичная

0000

0001

0010

0011

0100

0101

0110

0111

Десятичная

0

1

2

3

4

5

6

7

Двоичная

1000

1001

1010

1011

1100

1101

1110

НИ

Десятичная

8

9

10

11

12

13

14

15

Как мы можем представить число в кубитах?

Например, нам нужно представить число 9 (схема 2). В двоичной системе его эквивалентом будет 1001, так как вычислив 1 · 2^3 + 0 · 2^2 + 0 · 2^1 + 1 -20 (помним, что 20 = 1), получим 9.

Следовательно, |9> соответствует 11001>. А число 8? |8) соответствует 11000>. Это означает, что квантовый компьютер представляет числа 8 и 9 так же, как и обычный.

Однако он также может представлять и выполнять операции суперпозиции, например с |8> + |9>.

РИС. 2

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

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

У нас есть два кубита, которые обозначим А и В, в состояниях 0 и 1. Представим их, согласно системе счисления, в виде |0>A и |1>B соответственно. Если они запутаны, нужно использовать символ ®, применяемый в математике для обозначения операции тензорного произведения, как показано далее:

В предыдущем выражении 1/√2

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

(1/√2)2,

получаем 1/2. Это позволяет измерить состояния в квантовом эксперименте и получить результаты |01> или |10>.

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

РИС.З

В данном эксперименте интересно то, что если, например, Алан первым измерит состояние своего кубита (А), он узнает, что оно равно |0>A или |1>A, и вероятность того и другого события, как и при подкидывании монетки, составляет 50%. Однако фантастический аспект квантового исчисления состоит в том, что измерение Аланом кубита станет причиной коллапса, который произойдет после выяснения его состояния. В результате для Эндрю, находящегося в другой комнате, учитывая, что кубиты запутаны, эксперимент потеряет характер случайности. Если теперь Эндрю все же будет измерять свой кубит (В), результат его наблюдений заведомо известен. То есть для Эндрю результаты эксперимента уже не эквивалентны подбрасыванию монетки, так как в 100% наблюдений он получит результат, обратный результату Алана (схема 3). Например, если Алан увидел, что запутанный кубит А находится в состоянии |0>A, произойдет коллапс пары кубитов |0>A и |1>B. Если же Алан увидел обратную ситуацию, а именно что А находится в состоянии |1>A, тогда произойдет коллапс пары кубитов |1>A и |0>B. То есть измерения, проведенные Аланом, «изменили» кубиты таким образом, что однозначно определили наблюдения Эндрю.

Полезность квантовой запутанности в системах шифрования с военными или коммерческими целями очевидна, так как если два человека совместно владеют запутанными объектами, несанкционированное вмешательство в систему третьего лица изменит один из двух объектов и таким образом выдаст присутствие постороннего. Сегодня ведутся исследования в системах этого класса с использованием поляризованного света, волны которого совершают колебания в одной плоскости, при этом считается, что горизонтальные колебания соответствуют состоянию 0, а вертикальные — состоянию 1. Таким образом, в квантовом компьютере кубит может находиться в состояниях |0>, |1>, состоянии суперпозиции между |0> и |1> или может быть запутанным с другим кубитом, и это позволяет преодолеть ограничения универсальной машины Тьюринга, или, если угодно, компьютера.

Наконец, если комплектующие компьютера используют вентили И, ИЛИ и другие, в квантовом компьютере используются квантовые вентили, оперирующие кубитами, и их операции имеют реверсивный характер. Например, при использовании вентиля ИЛИ в обычном компьютере, если выход равен 1, выполненная операция не реверсивна. Это означает, что невозможно установить, какими были входные данные: 0 или 1,1 или 0,1 или 1. Кроме того, класс операций с кубитами, которые может совершать квантовый компьютер, выше, чем класс операций с битами, так как состояния, в которых может находиться кубит, могут быть представлены как вектор в сфере, называемой сферой Блоха (схема 4). Программа blochsphere симулирует один кубит, а также операции, которые можно с ним выполнить.

Кроме логических операторов булевой алгебры (И, ИЛИ и другие), возможны другие операции с кубитами, определяющие вращение вектора по осям X, Y, Z сферы Блоха. Эти операции являются результатом применения так называемых квантовых вентилей, то есть квантовых цепей, производящих операцию над одним или несколькими кубитами. Например, вентили Паули и Адамара позволяют совершать вращения. Необходимо помнить, что хотя кубит представлен в сфере Блоха как вектор, на самом деле квантовые операторы представляют матрицы, которые при умножении на вектор-кубит дают новый вектор — измененный кубит. Вот простой пример оператора Паули класса х с матрицей

При применении ее к кубиту произойдет вращение сферы Блоха по оси Х и изменение |0> на |1> и |1> на |0>. Это эквивалентно оператору НЕ на обычном компьютере. Вентиль Адамара представляет особый случай: вращение вектора происходит одновременно по осям X и Z:

Другие операторы, такие как контролируемое отрицание (CNOT), swap, вентиль Тоффоли, позволяют выполнять контролируемые операции с двумя или тремя кубитами.

РИС. 4

Сфера Блоха. Кубит представлен вектором |ψ>. Состояния |0> и |1> находятся на севере и юге сферы, в остальных частях сферы — состояния суперпозиции.

РИС. 5

Еще одной особенностью квантового компьютера является то, что операции выполняются параллельно, то есть одновременно по разным линиям, например по линиям L1 и L2, комплектующие квантового компьютера предусматривают соединение одного за другим квантовых вентилей (U; рисунок 5).

В 2011 году канадская фирма D-Wave Systems объявила о старте продаж первого коммерческого квантового компьютера под названием D-Wave One. По заверениям фирмы, компьютер обладал микропроцессором на 128 кубит. В том же году команда исследователей из США, Китая и Японии объявила, что такой класс компьютеров может быть построен в соответствии с моделью архитектуры фон Неймана. В 2012 году IBM также сообщила, что сделаны значительные успехи в создании машины с такими характеристиками. Больше чем через полвека повторяется сценарий, имевший место с ENI АС, Colossus и другими компьютерами. Однако это не совсем верно, так как строительство квантового компьютера является настолько сложным проектом, что разные страны объединили усилия, создав многонациональные команды и оставив в прошлом межнациональное соперничество. Ожидается, что квантовый компьютер найдет применение не только в криптографии: с его помощью станет возможным более реалистическое моделирование, например воздействия медикаментов на человека, а также выполнение расчетов в физике, химии, астрономии и решение масштабных математических задач, таких как факторизация больших чисел.

Скорее из любопытства ученые уже создали квантовые версии игры «Жизнь» Конвея. Также в последнее время были предложены различные модели искусственных нейронных цепей, в которых нейроны симулируются квантовыми операторами, что открывает путь для дальнейших исследований в области квантового искусственного интеллекта. Еще одним применением квантового компьютера может стать генерация истинно случайных чисел, которые будут не псевдослучайными, а будто бы вытащенными из лотерейного барабана. Уже сегодня интернет дает возможность получить случайные числа с помощью квантовых феноменов (см. www.randomnumbers. info).

ЭМУЛЯЦИЯ КВАНТОВОГО КОМПЬЮТЕРА

Сегодня мы можем создать только крайне усеченную версию квантового компьютера — с помощью обычного. Одним из таких примеров является jQuantum — программа, с помощью которой можно разработать элементарные цепи, используя стандартные квантовые операторы. Она позволяет разработать реестр данных, может хранить до 15 кубит, создать цепь и выполнить алгоритм.

МЕЧТА ТЬЮРИНГА: УМНЫЕ МАШИНЫ НА СЛУЖБЕ ЧЕЛОВЕКА

Внезапно оборвавшаяся в 1954 году жизнь Алана Тьюринга не позволила ему закончить исследования в Манчестерском университете. Он как раз приступил к разработке моделей нейронных цепей, с помощью которых можно изучать так называемые «умные» машины, учитывая особенности работы человеческого мозга. В год смерти Тьюринга двое исследователей из Массачусетского технологического института, Бельмонт Фарли (1920-2008) и Уэсли Кларк (р. 1927), успешно смоделировали на компьютере сеть из 128 нейронов, которые могли распознавать простые модели после фазы обучения. Ученые отметили, что при уменьшении количества нейронов на 10% сеть не теряла способностей к распознаванию. Конечно, модель была элементарной, она состояла из нейронов, соединенных друг с другом случайным образом, каждое соединение было связано с определенным весом, и нейронная цепь вела себя подобно сети Маккалока — Питтса. Ее обучение происходило в соответствии с правилом Хебба, то есть когда один нейрон постоянно стимулировал другой, их синаптическая пластичность возрастала, и вес соединения между обоими нейронами увеличивался. В 1956 году, через два года после смерти Тьюринга, Джон Маккарти использовал термин искусственный интеллект на конференции по компьютерной симуляции поведения человека. Через год, в 1957 году, психолог Фрэнк Розенблатт (1928-1971) разработал перцептрон — первую искусственную нейронную сеть, имеющую практическое применение.

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

ДНК И ЖИЗНЬ В КОМПЬЮТЕРЕ

В конце жизни Алан Тьюринг ставил передовые эксперименты по симуляции морфогенеза, то есть биологических процессов, протекающих при развитии организма. Для этой цели ученый использовал компьютеры Манчестерского университета. Тьюринг утверждал, что некоторые химические вещества (морфогены), физико-химические процессы (допустим, диффузия, то есть движение таких молекул, как морфогены), а также другие феномены, например активация или ингибиция (подавление), ответственны за процессы клеточной дифференциации, состоящей из этапов, которые проходит клетка от эмбриона до взрослого индивидуума. Центральной идеей была мысль о том, что положения, которые занимают недифференцированные, или неспециализированные клетки эмбриона, содержат записанную в морфогенах информацию, согласно которой морфогены контролируют развитие эмбриона. Этот процесс приводит к специализации клеток и превращению зародыша во взрослую особь. Так еще раз проявилась гениальность Тьюринга, предсказавшего существование морфогенов задолго до того, как они были открыты.

ЭМУЛЯЦИЯ ИСКУССТВЕННЫХ НЕЙРОННЫХ СЕТЕЙ

В настоящий момент модели искусственных нейронных сетей имеют широкое применение. В основном нейронные сети используют одну организационную модель: нейроны организованы слоями (вход, выход, возможны скрытые нейроны), их соединение осуществляется согласно определенному биологическому критерию — нейроны одного слоя соединяются с нейронами другого слоя. Пользователь устанавливает для сети пороги активации, функцию активации или передачи, другие параметры. И все же, несмотря на схожую организацию всех искусственных нейронных сетей, имеется один отличительный элемент — алгоритм обучения. В парадигме искусственного разума обучение — процесс, в результате которого нейронная сеть изменяет ответ, или выход, при определенном входе. Это изменение является результатом настройки одного или нескольких соединений и их веса. Существует множество методов настройки веса соединений сети, с помощью которых сеть обучается распознавать образцы (буквы, числа, фотографии и так далее). В других случаях сеть просто запоминает образец без обучения, то есть настройка веса соединений не требуется. Ни модель Маккалока — Питтса, ни модель Тьюринга не были способны к обучению, так как для этого потребовалась разработка специального алгоритма. Обучаемые модели могут эмулировать операторы И, ИЛИ и другие, то есть они ближе к машине Тьюринга, чем к биологической нейронной сети. Одна из лучших программ для изучения искусственных нейронных сетей — Штутгартский симулятор нейронной сети (SNNS).

Штутгартский симулятор нейронной сети (SNNS).

В 1960-е годы биолог Льюис Вольперт (р. 1929) усовершенствовал понятие морфогена, введенное Тьюрингом, после открытия первого белка, имеющего такие характеристики, у уксусной мушки Drosophila melanogaster. Морфогенами могут быть различные химические вещества, от белков до витаминов, в их функции входит контроль генов — наследственных единиц. Однако учитывая, что ген — фрагмент ДНК, его действие не было понятно до открытия структуры ДНК Джеймсом Уотсоном (р. 1928) и Фрэнсисом Криком (1916-2004) в 1953 году, за год до смерти Тьюринга. Сегодня модель морфогенеза Тьюринга, с помощью которой он объяснил формирование полосок на шкуре зебр, применена к другим животным и доказана экспериментально. Ее высоко оценили такие специалисты по теоретической биологии, как Льюис Вольперт и Ганс Мейнхардт (р. 1938). Однако некоторые исследователи утверждают, что механизм морфогенеза отличается от представленного Тьюрингом. На самом деле клетки эмбриона следуют определенному глобальному плану и специализируются вследствие серии трансформаций, которые можно объяснить их механическими свойствами.

Памятник Алану Тьюрингу в Садах Витворта в Манчестере. Яблоко в руке напоминает о способе самоубийства.

Марка в память об Алане Тьюринге, выпущенная в 2012 году.

Памятное изображение в честь столетия со дня рождения Алана Тьюринга, которое отмечалось в 2012 году.

ВИЗУАЛИЗАЦИЯ ДНК В JMOL

Jmol - Java-программа визуализации, с помощью которой можно увидеть трехмерные структуры химических соединений, кристаллов, материалов и биомолекул. Один из самых интересных примеров — молекула ДНК, ее можно поворачивать, увеличивать или уменьшать, менять тип изображения и так далее. ДНК — полимер, имеющий структуру двойной спирали из повторяющихся блоков, нуклеотидов — аденина (А), цитозина (С), гуанина (G) и тимина (Т). Нуклеотиды одной спирали составляют пары с нуклеотидами другой спирали: А с Т, G с С, определяя на каждой спирали последовательности — гены, в которых хранится биологическая информация, передаваемая из поколения в поколение.

Визуализатор Java Jmol.

Они могут деформироваться, растягиваться и даже превращаться в нейронные, мускульные или костные клетки. Этот комплекс трансформаций объясняют с помощью математического моделирования механических феноменов, наблюдаемых в клетках. Данную идею, так же как и модель Тьюринга, использующую дифференциальные уравнения, поддержали ученые Конрад Уоддингтон (1905-1975), Мюррей Гелл-Ман (р. 1929) и Брайн Гудвин (1931-2009).

После открытия ДНК и разработки алгоритма для изучения генетической информации с помощью компьютера появилась новая дисциплина — биоинформатика. Компьютер был и остается важным инструментом для изучения ДНК, но также с его помощью разработан новый класс компьютеров, изучение которых привело к выделению вычислительных систему использующих ДНК. В 1994 году Леонард Адлеман (р. 1945), осуществив ряд опытов с ДНК, решил задачу о гамильтоновом графе, состоящую в обнаружении кратчайшего маршрута, проходящего по каждому городу один раз. Количество городов является строго определенным — Адлеман рассмотрел случай с семью городами. Эти опыты открыли путь другим исследователям, среди них был и Эхуд Шапиро (р. 1955), построивший машину Тьюринга из молекулы ДНК.

ПРИЗНАНИЕ НАСЛЕДИЯ

В 1999 году журнал Time назвал Алана Тьюринга в числе 20 наиболее влиятельных личностей XX столетия. С 1966 года Ассоциация вычислительной техники, более известная под сокращением ACM, ежегодно вручает премию Тьюринга — награду по информатике, эквивалентную Нобелевской премии. В 2009 году Гордон Браун, премьер-министр Британии в то время, принес официальные извинения за несправедливое осуждение Алана Тьюринга. Однако в феврале 2012 посмертное прошение о помиловании, представленное палате лордов и собравшее 23 тысячи подписей, было отклонено.

В честь празднования 100-летия со дня рождения ученого 2012 год был назван Годом памяти Алана Тьюринга, в течение которого проводились юбилейные мероприятия, конференции и собрания по всему миру. В Соединенном Королевстве их было проведено больше всего. Также была выпущена памятная марка с изображением Bombe — машины, с помощью которой Алан Тьюринг и его коллеги расшифровали коды «Энигмы», сделав вклад в победу своей страны и союзников во Второй мировой войне.

В честь столетия со дня рождения Тьюринга научно-популярный журнал Scientific American посвятил ученому специальный номер, названный «Наука после Алана Тьюринга». Сегодня установлено пять «синих табличек», посвященных Алану Тьюрингу. В Британии подобные таблички устанавливаются на зданиях, где родился, жил или умер какой-либо великий деятель.

Список рекомендуемой литературы

Arbib, М.А., Cerebros, mdquinas у matemdticas, Madrid, Alianza Universidad, 1987.

Bell, E.T., Los grandes matemdticos, Buenos Aires, Losada, 2010.

Boyer, C., Historia de la matemdtica, Madrid, Alianza Editorial, 2007.

Coello, C.A., Breve historia de la computation у sus pioneros, Mexico D.F., FCE, 2003.

Crane, T., La mente mecdnica. Introduction filosofica a mentes, md- quinas у representation mental, Mexico D.F., FCE, 2008.

Isasi, P., Martinez, P., Borrajo, D., Lenguajes, gramdticas у automatas. Un enfoque prdctico, Madrid, Pearson Education, 1997.

Lahoz-Beltra, R., Bioinformdtica. Simulation, vida artificial e inteligencia artificial, Madrid, Diaz de Santos, 2004.

—: Turing. Del primer ordenador a la inteligencia artificial, Madrid, Nivola, 2009.

Leavitt, D., El hombre que sabia demasiado, Barcelona, Editorial Antoni Bosch, 2007.

Odifreddi, P., La matemdtica delsiglo xx: de los conjuntos a la complejidad, Buenos Aires, Katz Editores, 2006.

Pena, R., De Euclides a Java: Historia de los algoritmos у de los lenguajes de programacion, Madrid, Nivola, 2006.

Stewart, I., Historia de las matemdticas, Madrid, Critica, 2008.

Strathern, P., Turingy el ordenador, Madrid, Siglo XXI, 1999.

Указатель

автомат 46-49, 92, 104

клеточный 46, 47, 49, 138

конечный 22, 28, 34, 46-48

нейронный 47, 102-109, 136, 137

самовоспроизводящийся 92 4

Алгол 37

алгоритм 34-38, 40, 50, 70, 73, 88, 95, 112, 113, 117, 124, 125, 127, 135, 137, 141

квантовый 126, 127

свойства 34

алфавит 28, 30, 46, 57, 58

анализ числовой 86, 95

«Аполлон», проект 32, 33

Атанасофф, Джон Винсент 89, 90

байт 97

барабаны см. Bombe 57, 66

бесконечный ряд 19

биоинформатика 123, 141

биология 7, 8, 10, 11, 17, 102, 116, 117, 123, 137, 138

вычислительный подход 116

математика 117, 123 бит 71, 75, 106, 127, 129

операции 13, 37, 49, 55, 62, 68, 73, 74, 84, 88, 90, 94, 103, 104, 112, 129, 132-134

Блетчли-Парк 9, 11, 23, 51, 60-64, 68, 70-72, 75-77, 79, 81, 95, 112, 126, 130

Блох, сфера 132, 133 бомба 61, 63, 64

бомба атомная 73, 87, 92

Брока, Поль 103

булева алгебра 74, 75, 104, 106, 133

Бэббидж, Чарльз 81, 90

Вейнценбаум, Джозеф 114

вентиль

Адамара 135

квантовый 18-20, 38, 92, 123-127, 129, 131, 133, 134

Паули 135

вероятности теория 23, 73, 132, 133

Вирт, Никлаус 37

Вторая мировая война 7-9, 11, 22, 23, 27, 53, 55, 57, 59, 62, 68, 70, 76, 77, 81, 86, 90, 97, 142

вычисление 11, 22, 27, 34, 40, 116, 126, 129, 131, 141

ДНК 141

Национальный музей 77

«эффективный метод» 34

Гарднер, Мартин 46

Гедель, Курт 22, 24, 26, 27, 39, 124

гены 118, 138, 140

Гильберт, Давид 22, 26, 27, 130

голоса шифровка 64, 65

Дарвин, Чарльз 81

дедукция 26

ДНК 10, 25, 136, 138, 140, 141

Дойч, Дэвид 28, 123, 124

точка плавающая 84

зебры, образец шкуры 10, 118, 120, 137, 139

золотое сечение 117

игра «Жизнь» 46-49, 134

интуиция 25, 50, 114, 124, 125

искусственный интеллект 7, 9, 37, 68, 101, 102, 107, 111-115, 123, 126, 134, 136, 137

квантовый 134

поведенческий подход 110

сильный 114

символьный подход 112

слабый 114

субсимвольный подход 104

КАПЧА 7, 111

Каспаров, Гарри 112-114, 119

карта перфорированная 63

Килбурн, Том 95

Кларк, Уэсли 135

когнитивные науки 102

код 44, 53, 60, 69-71, 83, 87, 93, 94, 140

Бодо 70, 71

ключевой 44, 83, 93

машинный 44, 83, 93

Морзе 70

«Энигмы» 7, 11, 62, 142

компилятор 44, 93, 112

компьютер 7-11, 13, 22, 25-27, 32-34, 36, 38, 40-47, 49, 53, 70, 72-77, 79, 81-93, 95, 97, 99, 101-105, 109-117, 120, 123, 125, 127, 129, 132-136, 141

виртуальный 33, 83

квантовый 8, 10, 38, 123, 127, 129, 130, 132-135

Цузе 90

эмуляторы 85

АВС 89

Baby 23, 86, 89, 95

Bendix G15 86

Colossus 9, 10, 33, 72, 74-77, 79, 88-90, 95, 134

EDSAC 10, 82, 87, 89

EDVAC87, 89, 92, 93

ENIAC 10, 44, 77, 87-90, 92, 93, 136

Ferranti Mark I 11, 86, 89, 91, 97

Harvard Mark 190

IAS 92

Macintosh 83, 85, 88

Manchester Mark I (MADAM) 11, 95, 97, 102, 113

ORDVAC 92, 93

Packard-Bell PB250 86

Pilot ACE 7, 9-11, 76, 79, 82, 83, 85, 86, 88, 89

UNIVAC 182

ZX Spectrum 85

Конвей, Джон 46, 47, 134

Королевское общество 95, 114

криптография 68, 126, 129, 134

криптология 60 (см. криптография) кубит 127-133

лжец парадокс 24, 25

логика 20, 22-24, 33, 50, 70, 74, 75, 94, 102, 104

лямбда-исчисление 36

Маккалок — Питтс модель 103, 104, 108, 136, 137

Маккарти, Джон 37, 101, 136

Макмахон закон 87

маркер 40

математика прикладная 23, 88, 95

машина

дезорганизованная 103

индетерминистская 40, 46

конечных состояний 46

Лоренца — Lorenz SZ 40-42, 68, 70, 72, 76

программируемая 72, 88

Робинсона 72

самовоспроизводящаяся 92

состояния 29-32, 45

Тьюринга 7-11, 15, 17, 20, 22, 23, 27-30, 32-34, 36-47, 50, 64, 65, 68, 72, 73, 76, 81, 82, 84, 86, 88, 90, 96, 101-103, 106, 108-116, 123-126, 132, 135-138, 141

Тьюринга квантовая 38, 123, 124, 126

умная 68, 112, 114

умножения 50

универсальная 32-38, 46, 47, 73, 76, 82, 86, 90, 96, 103, 125, 132

«Энигма» 7, 11, 56-70, 72, 142

рефлектор 58, 60, 65

роторы 57, 58, 60, 61, 64, 65

стартер 60 Tunny 70

метод

двух направлений 83

Монте-Карло 92

Тьюринг 68

механика квантовая 18-20, 92, 124, 125, 127, 129

Дирак счисление 127

запутанность 50, 129, 132

интерференция 129

суперпозиция 127

модуль 33, 65

мозг 60, 64, 92, 102, 103, 112, 113, 118, 124-126, 135

искусственный 64, 112

человеческий 60, 102, 103, 112, 124, 125, 135

Мокли, Джон В. 88, 89

Морком, Кристофер 19, 124

морфогенез 11, 116-118, 120, 136, 138

морфогены 118, 138

Национальная физическая лаборатория 11, 81

Нейман, Джон фон 8, 20, 51, 73, 89, 90, 92

архитектура 9, 90, 92, 93, 134

нейрон 46, 60, 102-106, 108, 109, 136, 137

биологический 142

волокна тренировки 107

искусственный 9, 103, 106, 108, 137

искусственный квантовый 134

синапсис 108

соединение 88, 103, 106-108, 134-136

порог 104, 109

цепь 107, 118, 124, 135

невычислимый 50, 125

неполнота, теорема 22, 24, 39

Ньюман, Макс 11, 23, 74, 95

обучение 103, 114, 137

относительность 18, 19, 124

оператор 36, 37, 57, 58, 65-67, 71, 75, 94, 104, 108, 133

булев AND 75, 76, 88, 103-108, 132, 133, 137

булев NAND 104, 108

булев NOT 106, 108, 133

булев OR 71, 75, 76, 88, 103-107, 132, 133, 137

булев XOR 71

модуль 33, 65

тензорное произведение 130

оракул 40

орден Британской империи 71

память 27, 28, 30, 31, 33, 38, 44, 47, 75, 82-84, 88, 89, 95-97, 102, 114, 127

аккумулятор 88

вспомогательная 44, 97

лента 30, 31, 34, 44, 47, 75

лучевая трубка 82, 96, 97

магнитный барабан 97

основная 27, 88, 95-97

регистр 28, 29, 38, 111, 135

ртутная линия 82

трубка Уильямса 97

управление 83

RAM 27, 38, 44, 95, 97

ROM 89

парадокс 24, 25, 42

«Паскаль» 13, 37, 96

Пенроуз, Роджер 124

переход 29, 40, 45, 48, 49

правила 26, 27, 29, 48, 49, 129

переводчик функция 33

подсолнухи, эксперимент 116

Полани, Майкл 101

поляризованный свет 132

проблема 8, 16, 20, 26, 27, 34, 37, 38, 40-43, 49, 50, 111, 125, 141

вычисляемая 37, 125

определения 26

остановки 8

Entscheidungsproblem 23, 40, 49

программа 11, 25, 26, 28, 29, 32, 33, 35, 37, 38, 41-44, 46, 57, 73, 76, 81-84, 86, 88, 93-97, 105, 109, 112-115, 119, 125, 126, 132, 135

разум 16, 19, 20, 90, 102-104

Рамон-и-Кахаль, Сантьяго 102, 107

Рассел, Бертран 20, 23, 26

рассуждение 26, 42, 50, 113, 114

Режевский, Мариан 60, 61

ретрокомпьютинг 85

Розенблатт, Франк 136

Сейл, Тони 77

секретность официальная закон 77

сети искусственные нейронные 10, 11, 103, 104, 123, 134, 136, 137

тип В 103, 106, 107

симуляция 8, 10, 38, 45-47, 56, 73, 101, 107, 115, 117, 126, 134-136

морфогенез 11, 116-118, 120, 136, 138

поведение 30, 31, 101, 104, 106, 110, 111, 136

симулятор 33, 46, 56, 66, 127

система 7, 16, 18, 26, 27, 32, 44, 46, 56, 60, 62-65, 68, 70, 72, 73, 83, 88, 90, 96, 97, 128-130, 132

неполная 24

неполная по Тьюрингу 96

нумерация 88, 90, 128

оперативная 44, 46, 83

самореференсная 25

эксперт 113 AGC 32, 33

совесть 113, 124, 125

спамботы 111

таблица переходов 29, 30, 40

топология 23

Уайтхед, Альфред Н. 22, 24

Уилкс, Морис 83, 87

Уильямс, Фредерик 95-97

Улам, Станислав 92

Университет 20, 22, 63, 95, 96

Брандейский 45

Кембриджский 8, 11, 19, 20, 21, 23, 46, 62, 95, 101

Манчестерский 9, 11, 23, 86, 87, 91, 95, 97, 101, 102, 116, 135, 138

Оксфордский 125

Пенсильванский 87-89

Принстонский 11, 50, 51, 90

Уотсон, Томас Дж. 10, 63, 138

уравнения 11, 35, 88, 95, 120, 126, 141

реакция — диффузия 11, 118, 120

условное выражение 23, 89, 94

IF-THEN 89, 94

устройство

арифметико-логическое 94, 104

контрольное 94

Фарли, Бельмонт 135

Фейнман, Ричард 38, 127

Фибоначчи последовательность 116-118

Флауэрс, Томми 74, 75, 77

фотоны 129

функция 19, 22, 23, 29, 33, 36, 60, 73, 74, 82, 97, 109, 124, 137

ступенчатая 109

Хамерофф, Стюарт 126

Хебб правило 136

химия 17, 101, 118, 120, 126, 134

Ходжес, Эндрю 20, 22, 87, 130

Холлерит, Герман 63

холодная война 77, 86, 87

цикл 25, 67, 89, 94

странный 25

FOR-TO 89, 94

циклометр 61

Цузе, Конрад 90

чатботы 114

Чёрч, Алонзо 33, 36, 49, 50

числа 16, 23, 26, 41, 49, 51, 70, 72-74, 92, 97, 103, 116, 117, 125, 128, 129, 134-137

генератор 70, 73

квантовые 38, 124, 126, 127, 129, 135

натуральные 26

случайные 70, 72, 73, 92, 135

π 34, 125, 126

шахматы 9, 97, 101, 110, 112-114, 119

Шеннон, Клод 64

Шербиус, Артур 56

Эддингтон, Артур 18, 20, 124

Эккерт, Джон 88

электроника цифровая 75, 106

электронные лампы 72, 74, 75, 84, 87, 88, 90

диод 74, 75

тиратрон 75

транзистор 74, 75

триод 74

фотоэлектронный умножитель 75

язык 24, 27, 33, 34, 37, 41, 43, 46, 65, 74, 83, 84, 86, 93, 94, 96, 114, 128

Ассемблер 33

программирования 33, 84, 86, 93, 96

C++ 46

ACM 141

Autocode 112

BASIC-256 41, 43, 73, 83, 94, 105

Bombe 11, 63, 64, 66-69, 72, 142

crib 66

Delilah 64, 65, 68

ELIZA 114, 115

GC&CS 61

Golly 49

Java 46, 76, 140

LISP 36, 37

Lego 39

MS-DOS 46

OCR7, 105, 111

output 43, 44, 65, 73, 94, 107, 108

SIGSALY 64

Turing 4.1.1 96

Turochamp 113

TypeX 68

U-Boot 55-57, 62

UNIVAC 82, 89

Unix 44, 83

Алану Тьюрингу через 75 лет после его смерти, в 2009 году, были принесены извинения от правительства Соединенного Королевства за то, как с ним обошлись при жизни. Ученого приговорили к принудительной химической терапии, повлекшей за собой необратимые физические изменения, из-за чего он покончил жизнь самоубийством в возрасте 41 года. Так прервался путь исследователя, признанного ключевой фигурой в развитии компьютеров, автора первой теоретической модели компьютера с центральным процессорным устройством, так называемой машины Тьюринга. Ученый принимал участие в создании первых компьютеров и использовал их для расшифровки нацистских секретных кодов, что спасло много жизней и приблизило конец войны. Такова, по сути, трагическая история гения, которого подтолкнула к смерти его собственная страна, хотя ей он посвятил всю свою жизнь.

Content

Lahoz-Beltra Rafael Размышления о думающих машинах. Тьюринг. Компьютерное исчисление

Rafael Lahoz-Beltra Наука. Величайшие теории. Выпуск 15: Размышления о думающих машинах. Тьюринг. Компьютерное исчисление

Введение

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

Глава 2 Машины против кода.

Глава 3 Первые компьютеры: британские или американские?

Глава 4 Создание думающих машин

Глава 5 Наследие Алана Тьюринга

Список рекомендуемой литературы

Указатель