Двигатель тьюринга


Алан Тьюринг как «универсальный вычислитель» / Хабрахабр

Источник: geektimes.ru

В первой половине XX века, когда были изобретены первые вычислительные машины. Однако наряду с физически осязаемыми машинами появлялись и машины-концепции. Одной из них была «машина Тьюринга» — абстрактное вычислительное устройство, придуманное в 1936 году Аланом Тьюрингом — учёным, которого считают одним из основоположников информатики.

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

Детство, образование, увлечения
Родители Алана жили в индийском городе Чхатрапур. Отец — Юлиус Мэтисон Тьюринг представитель старого шотландского аристократического рода, работал в Имперской государственной службе. Мать — Сара Этель (урожденная Стони), была родом из Ирландии, из протестантской семьи англо-ирландского дворянства. Когда она ждала ребёнка, супруги решили переехать в Англию, чтобы он рос и воспитывался в Лондоне.

Там Алан Тьюринг и родился 23 июня 1912 года. У него был старший брат Джон. Государственная служба Юлиуса Тьюринга продолжалась и родителям Алана приходилось часто путешествовать между Гастингсом и Индией, оставляя двоих своих сыновей на попечение отставной армейской пары. Признаки гениальности проявлялись у Тьюринга с раннего детства.

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

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

В 11 лет он ставил вполне грамотные химические опыты, пытаясь извлечь йод из водорослей. Все это доставляло огромное беспокойство его матери, которая боялась, что увлечения сына, идущие вразрез с традиционным воспитанием, помешают ему поступить в Public School (английское закрытое частное учебное заведение для мальчиков, учеба в котором была обязательна для детей аристократов). Но её опасения оказались напрасны: Алан смог поступить в престижную Шербонскую школу (Sherborne Public School).

В шесть лет Алан Тьюринг пошёл в школу святого Михаила в Гастингсе, директор которой сразу отметила его одарённость. В 1926 году, в возрасте 13 лет, Тьюринг пошёл в известную частную школу Шерборн в городе Шерборн графства Дорсет. Его первый день в школе совпал со Всеобщей забастовкой 1926 года. Поэтому Тьюрингу пришлось преодолеть расстояние около 100 км от Саутгемптона до Шерборна на велосипеде, по пути он переночевал в гостинице.

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

О школьных успехах Алана красноречиво свидетельствует классный журнал, в котором можно найти, например, следующее

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

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

Университет
Из-за нелюбви к гуманитарным наукам Тьюринг недобрал баллов на экзамене и поэтому после школы поступил в Королевский колледж Кембриджа, хотя намеревался пойти в Тринити-колледж. В Королевском колледже Тьюринг учился с 1931 по 1934 год под руководством известного математика Годфри Харолда Харди.

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

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

Тогда Тьюринг, наверное, и не предполагал, что через несколько лет фон Нейман предложит ему место в Принстоне – одном из самых известных университетов США. Ещё позже фон Нейман, так же как и Тьюринг, будет назван «отцом информатики». Но тогда, в начале 30-х годов ХХ века, научные интересы обоих будущих выдающихся учёных были далеки от вычислительных машин – и Тьюринг, и фон Нейман занимаются в основном задачами «чистой» математики.

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

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

Он также находил отдых в интенсивных занятиях спортом – греблей и бегом. Марафонский бег останется его поистине страстным увлечением до конца жизни.

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

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

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

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

Машина Тьюринга
В 1928 году немецкий математик Давид Гильберт привлек внимание мировой общественности к проблеме разрешения (Entscheidungsproblem). В своей работе «On Computable Numbers, with an Application to the Entscheidungsproblem», опубликованной 12 ноября 1936 года. Тьюринг переформулировал теорему Гёделя о неполноте, заменив универсальный формальный арифметический язык Гёделя на простые гипотетические устройства, которые впоследствии стали известны как машины Тьюринга.

Он доказал, что подобная машина была бы способна произвести любые математические вычисления, представимые в виде алгоритма. Далее Тьюринг показал, что не существует решения Entscheidungsproblem, сперва доказав, что Проблема остановки для машины Тьюринга неразрешима: в общем случае невозможно алгоритмически определить, остановится ли когда-нибудь данная машина Тьюринга.

Хотя доказательство Тьюринга было обнародовано в скором времени после эквивалентного доказательства Алонзо Чёрча, в котором использовались Лямбда-исчисления, сам Тьюринг был с ним не знаком. Подход Алана Тьюринга принято считать более доступным и интуитивным. Идея «Универсальной Машины», способной выполнять функции любой другой машины, или другими словами, вычислить всё, что можно, в принципе, вычислить, была крайне оригинальной. Фон Нейман признал, что концепция современного компьютера основана на этой работе Алана Тьюринга. Машины Тьюринга по-прежнему являются основным объектом исследования теории алгоритмов.

На вопрос: «Что такое машина Тьюринга и какое отношение она имеет к программированию?» один из пользователей Toster ответил так:

В первую очередь — это формальное определение алгоритма. Задача считается алгоритмически разрешимой тогда и только тогда, когда её решение можно запрограммировать на машине Тьюринга (или каким-нибудь другим эквивалентным способом). Это определение даёт, например, возможность предъявить алгоритмически неразрешимые задачи. Позволяет ввести понятие «Тьюринг-полного» языка — если на языке можно реализовать машину Тьюринга, то на нём можно написать любой алгоритм (препроцессор языка С таким не является, а C# — является).

В общем, МТ — способ определить некоторый класс алгоритмов:

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

С сентября 1936 года по июль 1938 Тьюринг работал под руководством Чёрча в Принстоне. Кроме занятий математикой, учёный изучал криптографию, а также конструировал электромеханический бинарный умножитель.

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

Криптоанализ
Во время Второй мировой войны Алан Тьюринг принимал активное участие во взломе немецких шифров в Блетчли-парке. Историк и ветеран Блетчли-парка Эйза Бригс однажды сказал:

«Блетчли-парку был нужен исключительный талант, исключительная гениальность, и гениальность Тьюринга была именно такой».

С сентября 1938 года Тьюринг работал на полставки в GCHQ — британской организации, специализировавшейся на взломе шифров. Совместно с Дилли Ноксом он занимался криптоанализом «Энигмы». Вскоре после встречи в Варшаве в июле 1939 года, на которой польское Бюро шифров предоставило Великобритании и Франции подробные сведения о соединениях в роторах «Энигмы» и методе расшифровки сообщений, Тьюринг и Нокс начали свою работу над более основательным способом решения проблемы.

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

Машина, созданная на основе этой спецификации, искала возможные настройки, использованные для шифрования сообщений (порядок роторов, положение ротора, соединения коммутационной панели), опираясь на известный открытый текст. Для каждой возможной настройки ротора (у которого было 10 ^ 19 состояний или 10 ^ 22 в модификации, использовавшейся на подводных лодках) машина производила ряд логических предположений, основываясь на открытом тексте (его содержании и структуре).

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

Спецификация для «Бомбы» была только первым из пяти важнейших достижений Тьюринга в области военного криптоанализа.

Учёный также определил индикаторную процедуру ВМФ Германии; разработал более эффективный способ использования Bombe, основанный на статистическом анализе и названный «Банбурисмусом»; метод определения параметров колёс машины Лоренца, названный «Тьюринжерией»; ближе к концу войны Тьюринг разработал портативный шифратор речи Delilah.

Статистический подход к оптимизации исследований различных вероятностей в процессе разгадывания шифров, который использовал Тьюринг, был новым словом в науке. Тьюринг написал две работы: «Доклад о применимости вероятностного подхода в криптоанализе» и «Документ о статистике и повторениях», которые представляли для GCCS, а позже и для GCHQ (англ. Government Communications Headquarters) такую ценность, что не были предоставлены национальному архиву вплоть до апреля 2012 года, незадолго до празднования ста лет со дня рождения учёного. Один из сотрудников GCHQ заявил, что этот факт говорит о беспрецедентной важности этих работ.

Тьюринг занимался также разработкой шифров для переписки Черчилля и Рузвельта, проведя период с ноября 1942 года по март 1943 года в США.

В 1945 году Тьюринг был награждён орденом Британской империи королём Георгом VI за свою военную службу, но этот факт оставался в секрете многие годы.

Послевоенные годы
После того как фон Нейман в США предложил план создания компьютера EDVAC, аналогичные работы были развернуты в Великобритании в Национальной физической лаборатории, где Тьюринг проработал с 1945 года. Ученый предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), который, однако, так и не был реализован.

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

1947–1948 академический год Тьюринг провел в Кембридже. Пока Алан Тьюринг пребывал в Кембридже, Pilot ACE был построен в его отсутствие.

Franklin ACE 1200

Он выполнил свою первую программу 10 мая 1950 года. Хотя полная версия ACE никогда не была построена, некоторые компьютеры имели с ним много общего, к примеру, DEUCE и Bendix G-15.

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

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

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

Тест Тьюринга
В 1948 году Алан Тьюринг получил звание Reader в математическом департаменте Манчестерского университета. Там в 1949 году он стал директором компьютерной лаборатории, где была сосредоточена работа по программированию Манчестерского Марка I.

В то же время Тьюринг продолжал работать над более абстрактными математическими задачами, а в своей работе «Computing Machinery and Intelligence» (журнал «Mind», октябрь 1950) он обратился к проблеме искусственного интеллекта и предложил эксперимент, ставший впоследствии известным как тест Тьюринга.

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

В 1951 году Тьюринг был избран членом Лондонского королевского общества.

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

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

Данный мысленный эксперимент имел ряд принципиальных следствий. Во-первых, он предложил некоторый операциональный критерий для ответа на вопрос «Может ли машина мыслить?».

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

Следствием этого стала та важнейшая роль, которую в дальнейшем развитии искусственного интеллекта, во всяком случае, до 1980-х годов играли исследования по моделированию понимания и производства естественного языка. В 1977 году тогдашний директор лаборатории искусственного интеллекта Массачусетского технологического института П.Уинстон писал, что научить компьютер понимать естественный язык – это все равно, что добиться построения интеллекта вообще.

Источник: slideshare.net

Память
• именем ученого назван один из астероидов;

• ежегодная награда Ассоциации вычислительной техники называется Премией Тьюринга;

• на главной площади университета Суррея (Англия) есть статуя Тьюринга и одно из зданий факультета инженерных и физических наук названо в его честь;

• одна из аудиторий отдела информатики при Университете Лилль в Северной Франции назван в честь Алана М. Тьюринга;

• Манчестерский университет, Открытый университет, Университет Оксфорд Брукс и Университет Орхус (Дания) имеют корпуса имени Тьюринга и другие;

• в 2001 году в Манчестере был установлен памятник учёному.

habrahabr.ru

Полезности для вебмастеров и не только — xBB.uz

31.01.2015: Пессимизация. Что это такое и как избежать?

28.01.2015: 5 инструментов продвижения, которые больше не работают

26.01.2015: Простой способ прогнозировать посещаемость сайта

23.01.2015: Что такое верстка сайта и ее виды

21.01.2015: Объем контента сайта и его влияние на позиции в поисковой выдаче

Для вебмастеров

Пессимизация. Что это такое и как избежать? 31.01.2015 Одним из популярных способов продвижения является оптимизация текстового контента под поисковые системы. Это объясняется достаточно высокой эффективностью и относительной простотой. Но часто случается, что веб-мастера чрезмерно увлекаются оптимизацией текстов. Как результат, можно наблюдать переспам ключевых слов или другие злоупотребления. За такие проступки поисковые системы предусматривают наказание, именно оно имеет название пессимизация. 5 инструментов продвижения, которые больше не работают 28.01.2015 Поисковая оптимизация динамично развивается и при ее проведении нужно быть очень аккуратным. Те инструменты, которые недавно работали и давали результаты, могут оказаться бесполезными и вредными. Бывает и наоборот, когда методы, за которые можно было получить наказание от поисковых систем, начинают эффективно работать. Соответственно, оптимизатор должен всегда находиться в курсе тенденций и понимать, какие способы продвижения можно использовать. Простой способ прогнозировать посещаемость сайта 26.01.2015 Узнать будущую посещаемость сайта легко. Но зачем это делать? Если вы собираетесь использовать сайт как рекламную площадку, то еще до того, как приступать к его созданию, вам необходимо понять, сколько людей будут заходить на сайт в будущем. Вы оцениваете видимость сайта и потенциальный трафик по каждому из интересующих вас запросов, и на основании полученной информации создаете семантическое ядро. Это научный подход, который приносит результаты.

Для программистов

Программируем на R: как перестать бояться и начать считать 28.11.2014 Возможно, вас заинтересовала проблема глобального потепления, и нужно сравнить погодные показатели с архивными данными времен вашего детства. Калькулятором тут не обойтись. Да и такие программы для обработки электронных таблиц, как Microsoft Excel или Open Calc, пригодны только для простых вычислений. Придется изучать специализированный статистический софт. В этой статье мы расскажем об одном из популярнейших решений — языке программирования R. Smart Install Maker. Создаем установщик 23.11.2014 Появляется все больше инди-разработчиков, которые создают собственное программное обеспечение для компьютеров. Однако, чтобы продукт выглядел качественным, необходимо продумать все до мелочей, в том числе и систему установки программы. Тратить время на написание собственных инсталляторов никто не хочет, поэтому на рынке появляется все больше специализированных утилит, которые все сделают за вас. Они дают целевому пользователю то, что ему необходимо. Функции в языке программирования C++ 18.11.2014 Функцией называют обособленный модуль программы, внутри которого производятся некоторые вычисления и преобразования. Помимо непосредственных вычислений внутри данного модуля могут создаваться и удаляться переменные. Теперь расскажем о том, из каких основных частей состоит функция в C++. Самая первая часть — это тип возвращаемого значения. Он показывает, что будет передавать функция в основную программу после своих внутренних преобразований...

Для других IT-специалистов

Роль дизайна в разработке пользовательских интерфейсов 23.11.2014 Разработка программного обеспечения — сложный, трудоемкий процесс, требующий привлечения экспертов разного профиля. Команда опытных программистов способна создать систему, удовлетворяющую любым техническим заданиям заказчика. Однако зачастую вне зоны внимания остается существенный вопрос: а насколько привлекательна разработанная система для пользователя? К сожалению, на сегодняшний день разработчики не всегда готовы дать внятный ответ на этот вопрос. Аренда программного обеспечения 13.11.2014 В последнее время на рынке IT-услуг все большую популярность набирает услуга аренды серверных мощностей с размещенным на них программным обеспечением. Суть услуги состоит в том, что заказчику предоставляется доступ к необходимому программному обеспечению по модели «бизнес-приложения» в аренду. Базы пользователей располагаются на серверах в специально оборудованном дата-центре. Пользователи работают в программе через удаленный рабочий стол. Машина трехмерного поиска 09.11.2014 Поисковые машины, без которых немыслим современный интернет, еще довольно ограничены. Можно искать слова, изображения, а в последние годы и мелодии (по фрагменту, проигранному перед микрофоном). Но как найти, например, аромат яблока? Технологии цифровой обработки запахов пока не очень развиты. Однако есть прогресс в другом направлении — стал возможен поиск 3D-объектов. И судя по растущему количеству 3D-принтеров, это будет востребованный сервис.

Для других пользователей ПК и Интернет

YouTube и раритетные видеозаписи. Часть 2 19.01.2015 У скачанного файла *.MP4 напрочь отсутствует звук. Это просто кусок видеопотока, совершенно не проиндексированный, с некорректным заголовком. В Ubuntu воспроизвести его может лишь Gnome MPlayer, да и то без перемотки, без задействования пауз, строго подряд и непрерывно. Из всех бесплатных редакторов, доступных для Ubuntu Linux, переварить такое видео согласился лишь OpenShot. Импортировал и разместил на TimeLine (в области монтажа) без проблем. YouTube и раритетные видеозаписи 17.01.2015 В давние времена много чего записывалось на древние видеокассеты (VHS), большие плоские коробки с рулоном плёнки внутри. Затем контент оцифровывался и попадал на сервис YouTube, ставший для меломанов одним из основных источников добычи старых видеоклипов и концертов. Но пришла беда. Теперь почти все средства скачивания предлагают для загрузки лишь «360p». Этого разрешения хватит для просмотра разве что на маленьком экране телефона в четыре дюйма. Биржи контента. Ситуация к началу 2015 г. Обзор и тенденции. Часть 2 14.01.2015 Требования к качеству статей неуклонно растут. Хозяева бирж приспосабливаются к этому по-разному. Кто-то хитрит и придирается к чему может. Кто-то снижает уникальность из-за одного единственного технического термина в статье. А кто-то, не в силах придумать благовидные способы, просто блокирует и грабит пользователей. Во-вторых, биржи контента всё больше ориентируются на выполнение заданий, а продажа готовых статей становится второстепенной.

Для мобильных пользователей

Обзор смартфона Lenovo S580 26.11.2014 В этой статье подробно рассмотрен очередной смартфон Lenovo. Одним из направлений компании является выпуск смартфонов в доступном ценовом сегменте и с достойными характеристиками. Такой моделью и является S580. Качественный дисплей, хорошая камера, нестандартные 8 Гб памяти и производительный процессор обрекают этот смартфон на успех. В ближайшие месяцы он станет хитом продаж. Рассмотрим его внешний вид, функционал, характеристики, время работы. Firefox OS глазами пользователя. Часть 2 22.11.2014 К данному моменту Firefox OS вполне стабильна (по-настоящему) и вполне пригодна для использования теми, кому от смартфона нужны лишь базовые умения. Звонить умеет, Wi-Fi работает, смотреть видео и фотографии можно. Однако о покупке телефона с Firefox OS лучше не думать до тех пор, пока в местных магазинах не начнёт рябить в глазах от таких аппаратов. Ведь тогда и хороший выбор приложений появится, и дизайнеров Mozilla отыщет и на работу примет. Firefox OS глазами пользователя 22.11.2014 Мировосприятие многих сторонников Open Source основано на перманентном ожидания новинок. Когда-нибудь что-то разработают, выпустят, допилят, обвешают плюшками — реальность состоит лишь из надежд на счастливое будущее в заоблачных далях. Мы же в эти самые дали слегка заглянем и посмотрим на Firefox OS глазами ординарного пользователя. После чего, возможно, какие-то надежды развеются и растают, однако истина дороже. Рассматривать будем релиз 2.0.

Все публикации >>>

Последние комментарии

Все комментарии >>>

xbb.uz

Машина Тьюринга

Маши́на Тью́ринга (МТ)— абстрактный исполнитель (абстрактная вычислительная машина). Была предложенаАланом Тьюрингомв1936 годудля формализации понятияалгоритма.

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

Устройство машины Тьюринга

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

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

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

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

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk(если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо ajзаписывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример машины Тьюринга

Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:

Набор правил

Набор правил

q0*→q0R

q4a→q4aR

q01→q0R

q4=→q4=R

q0×→q1×R

q41→q41R

q11→q2aR

q4*→q51R

q21→q21L

q5*→q2*L

q2a→q2aL

q6a→q61R

q2=→q2=L

q6×→q7×R

q2×→q3×L

q7a→q7aR

q31 → q4aR

q71→q2aR

q3a→q3aL

q7=→q8=L

q3*→q6*R

q8a→q81L

q4×→q4×R

q8×→q9H

Умножим с помощью МТ 3 на 2 в единичной системе:

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

Полнота по Тьюрингу

Основная статья:Полнота по Тьюрингу

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

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

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

Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины Dи входные данныеX, которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данныеX.

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

На машине Тьюринга можно имитировать машину Поста,нормальные алгоритмы Марковаи любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называютсяполными по Тьюрингу(Turing complete).

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

Варианты машины Тьюринга

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

Машина Тьюринга, работающая на полубесконечной ленте

В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.

Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

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

studfiles.net

Машина Тьюринга | Планета информатики

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

Что собой представляет машина Тьюринга?

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

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

  • Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
  • Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
  • Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

  • Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
  • Передвигаться на одну ячейку влево или вправо.
  • Менять свое внутреннее состояние.

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

Пример работы машины Тьюринга

Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).

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

Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние q2 (команды которого совпадают с командами q1 предыдущей программы).

Изображения, использованные в статье

www.inf1.info

«Машина Тьюринга» – предок современного компьютера. Вселенная Алана Тьюринга

«Машина Тьюринга» – предок современного компьютера

Внимание Алана давно привлекала новая проблема, находящаяся в самом сердце математики, но что более важно – проблема, которая нашла отклик и в его сердце. Решение этой проблемы не требовало знаний, приобретенных по учебной программе, и затрагивало только всеобщие знания о природе вещей. Но такая, на первый взгляд, крайне заурядная проблема привела его к идее, впечатлившей многих. В 1935 году Алан начал размышлять о машинах.

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

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

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

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

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

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

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

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

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

– записать новый (заданный) символ в пустую ячейку, или оставить уже записанный символ в неизменном виде, или стереть символ и оставить ячейку пустой;

– остаться в прежней конфигурации или сменить ее на другую (заданную) конфигурацию;

– переместиться на ячейку влево, или вправо, или остаться в текущей позиции.

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

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

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

Более того, Алан пришел к другому важному удивительному выводу: в такой «машине» между «числами» и производимыми с ними операциями не было никакого существенного различия. С точки зрения современной математики, все они представляли собой лишь символы.

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

И самое главное – Алану удалось доказать, что математика никогда не будет исчерпана никаким конечным множеством операций.

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

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

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

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

«Теперь мы можем сконструировать машину, – писал далее Алан, – чтобы выполнить работу этого компьютера». Смысл его рассуждений был очевиден: каждое состояние вычислителя представлялось в виде конфигурации соответствующей машины.

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

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

Вся работа была выполнена им самостоятельно, ни разу он не обратился с обсуждением строения его машин к Ньюману. Лишь однажды он коротко обсудил теорему Геделя с Ричардом Брейтуэйтом во время ужина за профессорским столом. В другой раз он задал вопрос о методе Кантора молодому члену Совета Кингз-Колледжа Алистеру Уотсону (как оказалось, стороннику коммунистов), который только недавно сменил свою область интересов с математики на философию. Он поведал о своих мыслях Дэвиду Чамперноуну, и тот ухватил суть идеи создания универсальной машины, но с издевкой заметил, что такая машина уместится только в здание Алберт-Холла. Это замечание было довольно справедливым и было принято во внимание, поскольку если у Алана и имелись мысли представить свою идею, предложив практическое ей применение, то в самой статье их уже не было. Его «машина» не имела ни одного очевидного аналога в 1936 году, если только в общих чертах вобрала в себя некоторые черты изобретений, появившихся с развитием электротехнической промышленности: телетайпы, телевизионная разверстка изображения, автоматическая телефонная связь. Это было полностью его собственное изобретение.

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

* * *

Между тем смерть Георга Пятого ознаменовала собой переход от протеста против старого порядка к страху перед тем, что могло ожидать впереди. Германия уже победила новое Просвещение и поставила железное клеймо на идеалистах. В марте 1936 года был снова оккупирован Райнленд, и это означало только одно: будущее теперь зависело от политики усиления военной мощи и подготовки к войне. Кто тогда мог увидеть во всем этом связь с судьбой кембриджского математика? И все же связь была, поскольку однажды Гитлер потеряет Райнленд, и именно тогда универсальная машина сможет найти в мире свое практическое применение. Но между идеей машины Тьюринга и ее воплощением произойдет страшное, в результате чего жертвами станут миллионы людей. И жертв не станет меньше даже после свержения власти Гитлера.

* * *

…Алан представил свою работу для публикации Лондонскому математическому сообществу 28 мая 1936 года. Однако в Англии не нашлось ни одного человека, который смог бы отрецензировать работу Тьюринга для публикации в журнале. Ни один из корифеев науки не удосужился обмолвиться хоть словом. В случае же основного читателя журнала Лондонского математического общества Proceedings существовало сразу несколько причин, почему работа Алана не могла заинтересовать его в полной мере. Математическая логика оставалась отчасти периферийной темой для исследований, в которой сами математики обычно видели или попытку доработать то, что и так всем известно, или попытку создать новые проблемы на пустом месте. Начало работы казалось увлекательным, но после (типичным для Тьюринга образом) текст заводил читателя в непролазные дебри рядов непонятных готических символов, объясняющих устройство таблиц его универсальной машины. И в последнюю очередь этим могли заинтересоваться специалисты прикладной математики, которые обычно прибегают к практическому вычислению в таких областях, как астрофизика и гидроаэромеханика, где уравнения не приводят к решениям в явном виде.

* * *

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

В числе людей, ценивших такой подход, был Дональд Мичи, которому, как классицисту, мысли и идеи Алана импонировали, как свежие и новые. Он очень подружился с Тьюрингом, и они по пятничным вечерам стали встречаться в пабе в Стоуни-Стратфорде, чуть к северу от Блетчли-парка, чтобы поиграть в шахматы и поговорить или – что чаще предпочитал Дональд – послушать. Игра профессора в шахматы всегда была в Блетчли предметом шуток, все чаще сводившихся к пристрастному сравнению с приезжавшими шахматистами. Гарри Голомбек пожертвовал ему королеву и все равно выиграл; а когда ему сдался Алан, профессор перевернул шахматную доску и добился победы из положения почти безнадежного. Он посетовал, что Алан понятия не имел, как заставить части работать вместе, и слишком много раздумывал над своими действиями, чтобы играть свободно (что, может быть, проявлялось и в его социальном поведении). По выражению Джека Гуда, Алан был слишком продуманным, чтобы воспринимать, как очевидные и прозрачные, ходы, которые другие могли делать, не думая. Он всегда все обдумывал с самого начала. Был один замечательный случай, когда Алан вышел в ночную смену (это произошло в конце 1941 г.), а рано утром сел играть партию с Гарри Голомбеком. Заглянувший в комнату Тревис, сильно смешался, увидев это – он подумал, что его старший криптоаналитик играет в рабочее время. «Хм…гм… не думал вас застать за таким занятием, Тьюринг», – сказал он смущенно, как заведующий пансионом при школе, застукавший старшеклассника с сигаретой в туалете. «Надеюсь, вы обыграете его», – добавил он Голомбеку, когда они выходили из комнаты, ошибочно решив, что ас криптоанализа был первоклассным шахматистом. Но молодой Дональд Мичи был игроком под стать Алану.

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

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

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

* * *

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

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

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

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

Это был другой, но отнюдь не несочетающийся подход к идее «мозга». Именно взаимосвязь между двумя подходами, возможно, более всего воодушевила Алана – совсем как в Блетчли велась постоянная игра между человеческим разумом (агентурной разведкой) и использованием машинных, или «рабских» методов. Его теория «совокупности доказательств» показала, как преобразовывать определенные виды человеческого распознавания, суждений и решений в форму «записи инструкций». Его методы игры в шахматы поднимали вопрос: где можно было бы прочертить линию между «разумным», осмысленным, и «механическим»? Его точка зрения, выраженная с позиции принципа имитации, заключалась в том, что такой линии не было, да и никогда он не проводил резкого различия между «состоянием ума» и «записью инструкций», как двумя подходами к проблеме согласования понятий свободы и детерминированности.

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

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

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

Он понял, как создать мозг – не электрический мозг, как он, возможно, воображал себе до войны, а электронный мозг. И где-то в 1944 г. мать Алана слышала, как он рассказывает о «своих планах по созданию универсальной машины и о том вкладе, которое такая машина могла бы оказать психологии в изучении человеческого мозга».

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

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

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

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

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

И не успел! Американцы опередили Алана, создав ЭДВАК – Электронный дискретный переменный компьютер. Автором был давний знакомый Алана – Джон фон Нейман.

30 января 1945 г. фон Нейман написал, что ЭДВАК проектировался для решения трехмерных «аэродинамических задач и проблем ударных волн… расчета воздействий снарядов, бомб и ракет… в области метательных и бризантных взрывчатых веществ». Предварительный доклад о машине ЭДВАК пронизывал (отражая интересы фон Неймана) более теоретический рефрен, привлекавший внимание к аналогии между компьютером и нервной системой человека. И одним из инструментов для этого служило слово «память». В таком ключе это действительно оказывалось «созданием мозга». Однако, акцент доклада был сделан не на абстрактном тезисе о «состоянии ума», а на сходствах механизмов ввода/вывода данных и афферентных (чувствительных, центростремительных) нервов и эфферентных (двигательных, центробежных) нервов соответственно. Доклад также апеллировал к статье чикагских неврологов Уоррена Маккалока и Уолта Питтса (1943 г.), в которой активность нейронов анализировалась логическим языком, и использовал их символизм для описания логических связей электронных компонентов.

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

* * *

Но Алана эта неудача не остановила. Вскоре он придумал для нового проекта электронной вычислительной машины Тьюринга более счастливый акроним, в сравнении с бездушным ЭДВАК: АВМ – «Автоматическая вычислительная машина». И она стала более универсальной, чем ЭДВАК.

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

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

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

АВМ не должна была «решать арифметические задачи» так, как их решал бы человек. Она должна была лишь имитировать арифметические действия в том смысле, что при вводе команды, представляющей «67 + 45», можно было гарантированно получить на выходе «112». Но внутри машины не было «чисел», только импульсы.

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

* * *

Алан видел будущее своего детища. Например, так он рассматривал возможность использования удаленных терминалов: «…автоматическая вычислительная машина будет выполнять работу примерно за 10 000 вычислителей (людей). Поэтому логично ожидать, что большой объем вычислений, производимых вручную, сведется к нулю. Вычислители (люди) будут и в дальнейшем выполнять на маленьких счетных машинах такие действия, как подстановка значений в формулы, но, если на одно какое-либо вычисление у вычислителя уходит несколько дней работы, то лучше, чтобы его вместо человека выполняла электронная вычислительная машина. Но при этом совсем необязательно будет, чтобы у всех, кто заинтересован в такой работе, имелся компьютер. Целесообразно и возможно будет наладить управление удаленным компьютером с помощью телефонной связи. Для использования на этих удаленных станциях будут разработаны специальные устройства ввода и вывода информации, которые будут стоить, самое большее, несколько сотен фунтов стерлингов».

Алан также осознал требования к компьютерным программистам: «Основной объем работы, выполняемой этими компьютерами, будет состоять из задач, которые невозможно решить путем вычислений вручную в силу их масштабности. Чтобы загрузить машину такими задачами, нам потребуется большое количество способных математиков. Эти математики нужны будут для предварительной обработки и оформления задач для вычисления…»

И он на самом деле смог предугадать развитие новой отрасли промышленности и занятости:

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

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

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

АВМ смогла бы выполнить всю рутинную умственную работу для нужд британского фронта. Огласив такой вывод, Алан заработал себе необычно хороший «политический» балл: в перечне возможных приложений «создание таблиц стрельбы» стояло первым. Это была работа, для которой специально спроектировали ЭНИАК (первый электронный цифровой компьютер общего назначения, который можно было перепрограммировать для решения широкого спектра задач. – Ред.). Затем следовали еще четыре примера практического применения АВМ для вычислений, которые на тот момент требовали месяцы, а то и годы работы за арифмометрами. А еще четыре примера были не связаны с численными вычислениями; они отражали более широкий взгляд Алана на сущность компьютера, опыт и спектр интересов Тьюринга.

Первым значился компьютер, интерпретирующий специальный, предметно-ориентированный язык для описания электрических проблем:

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

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

«Машина, – писал Алан, – отлично справилась бы с этим делом; только не подходящее оно для нее. Скорость, с которой это можно было бы сделать, ограничивалась бы скоростью прочитывания карт. Такую работу может и должно делать с помощью обычной счетной машины Холлерита».

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

* * *

Поделитесь на страничке

Следующая глава >

biography.wikireading.ru

Машина Тьюринга - это... Что такое Машина Тьюринга?

Художественное представление машины Тьюринга

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

Устройство машины Тьюринга

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

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

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

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

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример машины Тьюринга

Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:

Набор правил Набор правил
q0*→q0*R q4a→q4aR
q01→q01R q4=→q4=R
q0×→q1×R q41→q41R
q11→q2aR q4*→q51R
q21→q21L q5 →q2*L
q2a→q2aL q6a→q61R
q2=→q2=L q6×→q7×R
q2×→q3×L q7a→q7aR
q31 → q4aR q71→q2aR
q3a→q3aL q7=→q8=L
q3*→q6*R q8a→q81L
q4×→q4×R q8×→q9×H

Умножим с помощью МТ 3 на 2 в единичной системе:

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

Полнота по Тьюрингу

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

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

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

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

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

На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).

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

Варианты машины Тьюринга

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

Машина Тьюринга, работающая на полубесконечной ленте

В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.

Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

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

Двумерные машины Тьюринга

См. также

Другие абстрактные исполнители и формальные системы вычислений

Ссылки

Литература

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1

dic.academic.ru

Машина Тьюринга

Машина Тьюринга

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

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

Задание работы машины Тьюринга можно описать программой – таблицей. В каждой клетке программы нужно указать, какие операции должен выполнить автомат, если, находясь в некотором состоянии, он "видит" данную букву. В общем случае, автомат, находясь в состоянии и обнаружив в ячейке букву, записывает в ту же ячейку заданную букву . Затем автомат выполняет движение , после чего переходит в состояние.Символ движения –это один из следующих трех символов: – автомат сдвигается на одну ячейку влево,– остается в той же ячейке,– сдвигается на одну ячейку вправо. Теперь следующее действие автомата нужно искать в строке, соответствующей состоянию, на пересечении со столбцом, соответствующим той букве, которую автомат "увидит" после сдвига. Считаем, что перед началом выполнения программы автомат находится в состоянии. В процессе своей работы машина Тьюринга будет как бы перескакивать из одной клетки программы в другую в соответствии с информацией на ленте и указаниями в клетках программы, пока не дойдет до клетки останова, в которой будет написано, что автомат должен оставить в очередной ячейке находящуюся там букву, остаться неподвижным и сохранить свое прежнее состояние. Клеток останова в программе может не быть; тогда машина Тьюринга никогда не остановится. Даже, если такие клетки есть, машина может никогда до них не дойти (ведь ее переходы зависят от программы и от входного слова). Если машина Тьюринга никогда не остановится, то считается, что она неприменима к данному входному слову. Она применима к слову только в том случае, если, начав работу над этим входным словом, рано или поздно дойдет до клетки останова.

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

Машина Тьюринга правильно вычисляет частичную функцию , если для любоговыполнено:

  1. Если определено и, то машина Тьюринга применима к начальной конфигурациии заключительной конфигурацией является.

  2. Если не определено, то машина Тьюринга неприменима к начальной конфигурации.

Здесь – множество всех слов конечной длины в алфавите.

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

Пример машины Тьюринга, которая переводит начальную конфигурацию в заключительную конфигурацию.

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

Тезис Тьюринга. Всякий алгоритм может быть реализован соответствующей машиной.

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

Нормальный алгоритм Маркова

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

Нормальный алгоритм Маркова представляет собой упорядоченный набор подстановок (продукций) вида

Формула подстановки служит для замены подслов в преобразуемом слове. Заменяемое и замещающееся подслова в формуле разделяются одной из стрелок → или • →. Продукция вида называется простой, а продукция– заключительной. В левой и правой частях формулы подстановки могут содержаться пустые слова. Для записи алгоритмов Маркова не требуется специального обозначения пустого слова, так как в этой конструкции носитель информации не зафиксирован, а преобразуемое слово свободно раздвигается и сдвигается. Заметим, что первое вхождение пустого слова находится слева от преобразуемого слова.

В качестве примера приведем алгоритм вычисления функции в алфавите(в алгоритме пустой символ обозначен как):

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

– либо все формулы оказались неприменимыми,

– либо на последнем шаге была применена завершающая формула, в которой левое и правое подслова разделяет стрелка →.

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

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

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

Нормальный алгоритм вычисляет частичную функцию, если он каждое словопереводит в словов случае, еслиили– неопределенно, если. Функция называетсявычислимой по Маркову, если существует нормальный алгоритм Маркова ее вычисляющий.

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

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

studfiles.net


Смотрите также