«Здесь родился Алан Тьюринг, пионер кибернетики и взломщик кодов» – гласит надпись на мемориальной доске, украшающей стену бывшей лечебницы, а ныне – одной из лондонских гостиниц. Имя отца информатики не просто высечено в камне: им названы самая престижная премия в этой области, тест на искусственный интеллект, а также одно из самых важных изобретений XX века – машина Тьюринга – краеугольный камень вычислительных машин и головная боль студентов мехмата.
Машина Тьюринга – гипотетический (хотя гики создают вполне реальные варианты из всего, что попалось под руку, – даже из конструктора LEGO) простейший вычислительный механизм, суть которого ученый сформулировал еще в университете, в своей работе о проблеме вычислимости («On Computable Numbers, with an Application to the Entscheidungsproblem»). Математики нашли эту идею настолько удачной, что даже само понятие «алгоритм» сейчас формализовано как нечто, что может быть запрограммировано на машине Тьюринга. Более того, самим ученым было доказано, что любые вычисления, которые производятся на устройстве, выполняющем последовательность элементарных действий, можно сделать также на машине Тьюринга, что легло в основу важного для информатики понятия полноты по Тьюрингу (к примеру, большинство современных языков программирования – тьюринг-полные).
Формальное описание машины довольно простое: она состоит из разделенной на ячейки бесконечной ленты и управляющего автомата. Управляющее устройство может двигаться по ленте влево или вправо, а также работать с той ячейкой, над которой находится, – читать и записывать «буквы» некоего конечного алфавита. Поведение управляющего устройства меняется в зависимости от его внутренних состояний, конечное множество которых заранее определено. Математики называют набор состояний управляющего устройства конечным автоматом. Каждому состоянию соответствуют действия машины в зависимости от символа в текущей ячейке. Действия обычно записывают в виде 3 частей: символ, который нужно записать, направление движения управляющего автомата и номер состояния, в которое автомат должен перейти. Кроме того, иногда выделяют также конечное, терминальное состояние машины – переход в него означает, что алгоритм выполнен.
Собранная энтузиастами из конструктора LEGO машина Тьюринга теоретически способна решать те же задачи, что и современный компьютер
Как можно понять, даже простейшие действия выражаются довольно громоздкими машинами Тьюринга. Сей факт породил понятие «Тьюринговой трясины» – так называют языки программирования, в которых элементарные вещи выражаются большим количеством кода. При этом машина Тьюринга считается одной из простейших вычислительных машин – именно потому, что у нее так мало возможных действий: чтение/запись значения в текущей ячейке, движение и изменение внутреннего состояния. А вот современный процессор – очень сложная машина: например, система команд вышедшего в 1978 году 16-битного микроконтроллера Intel 8086 содержала 82 инструкции (не считая вариаций отдельных из них). Из простоты машины Тьюринга происходит и ее основное достоинство – удобство использования в математических доказательствах и выкладках. Существует несколько разделов математики, прежде всего – теория алгоритмов и теория вычислимости, – в которых простая машина Тьюринга играет ключевую роль, ведь она эквивалентна любому другому вычислительному устройству, а описывать ее все же намного проще, чем архитектуру любого современного компьютера. Тем не менее, последние, в подавляющем большинстве использующие архитектуру фон Неймана, являются, по сути, далекими потомками гипотетических машин Тьюринга. Да и сама статья Джона фон Неймана, в которой он предложил идею компьютера с хранимой программой, включала много идей Тьюринга. А в 1946 году ученый сам опубликовал работу, в которой впервые было приведено детальное описание вычислительной машины, основанной на таком подходе.
Кроме создания и развития теоретического аппарата вычислительных машин, Тьюринг посвятил несколько лет своей жизни созданию машин вполне реальных – он принимал активное участие в работе британской Правительственной школы кодов и шифров в Блетчли-Парке. Опираясь на работы польских математиков, Тьюринг разработал метод дешифровки сообщений немецких машин «Энигма», на основе которого были созданы электронно-механические машины Bombe, расшифровывавшие послания немецкого ВМФ, сухопутных войск и даже разведки. Благодаря Тьюрингу были расшифрованы сообщения, содержащие информацию о готовящемся нападении на СССР. Несмотря на гриф секретности Ultra, наложенный на операцию по взлому шифра «Энигмы», и рискуя раскрытием источника данных, Британия все-таки передала информацию о планах Третьего Рейха советскому правительству. Однако Сталин не поверил в возможность нападения...
После успешного взлома кода «Энигмы» Тьюринг вместе с другими криптоаналитиками Блетчли-Парка занялся шифровальной машиной «Лоренц», которая применялась для обеспечения секретности переговоров высшего немецкого командования. В начале 1942 года были расшифрованы первые сообщения, защищенные этим кодом. Перехваченная информация включала и подробные планы наступления немцев на Восточном фронте, что позволило советским войскам подготовиться к битве на Курской дуге. А к 1944 году, с помощью опытного электронщика Томаса Флауэрса, был построен «Колосс» – 1500-ламповый компьютер для быстрой расшифровки сообщений, закодированных с помощью «Лоренца». Модернизированный вариант «Колосса» считается первым в мире программируемым компьютером.
По проекту Алана Тьюринга в 1946 году был создан первый британский компьютер с хранимой в памяти программой
Конец блестящей карьере положил скандал. В 1952 году квартиру Тьюринга обокрали, и, как оказалось позже, к ограблению был причастен его любовник. Из жертвы ученый тут же превратился в преступника: в те годы британское общество крайне негативно относилось к однополой любви. В итоге Тьюринг был осужден за гомосексуализм по так называемой поправке Лабушера (согласно ей же в 1895 году был приговорен к двум годам каторжных работ Оскар Уайльд). Власти предоставили ему выбор – тюрьма или гормональная терапия для подавления либидо. В надежде продолжить труд на благо науки Тьюринг выбрал последнее. На протяжении курса инъекций синтетического эстрогена, который длился год и вызвал у ученого импотенцию и рост груди, Тьюринг говорил, что «выйдет из этого лечения другим человеком, правда, еще не понятно, каким именно».
А 8 июня 1954 года Алан Тьюринг был найден мертвым в своей квартире. По данным следствия, он умер от отравления цианидом, который ввел в яблоко (авторы биографии ученого настаивают, что именно это яблоко большой поклонник Тьюринга по имени Стив Джобс годы спустя сделал логотипом своей компании). Правда, некоторые исследователи все же предполагают, что причиной смерти Тьюринга могло быть просто неосторожное обращение с химикатами.
Как бы то ни было, в 2009 году премьер-министр Великобритании публично принес извинения за преследования Алана Тьюринга. А нам осталось лишь читать исследования да наслаждаться результатами труда этого великого математика, который сыграл важную роль в закладке фундамента здания современной информатики.
В своей статье «Вычислительные машины и разум» Алан Тьюринг предложил идею гениального в своей простоте теста на искусственный интеллект: судья общается посредством текстовых сообщений с двумя собеседниками – человеком и компьютером. Задавая вопросы и получая на них ответы, он должен определить, кто из собеседников человек. Задача компьютера в данной ситуации – ввести судью в заблуждение своими ответами. Согласно утверждению Тьюринга, машина обладает интеллектом, если смогла обмануть судей в 30 % случаев. С одной стороны, философы и эксперты по искусственному интеллекту часто критикуют тест Тьюринга за непрактичность и подмену реального интеллекта симуляцией человеческого общения, с другой же – наличие столь просто формулируемого и проводимого теста – в особенности при отсутствии четкого понятия «интеллект» – привлекает энтузиастов. Каждый год проводятся соревнования, в которых множество программ пытаются обмануть коллегию судей и затеряться среди реальных людей. К примеру, в 2012 году программа «Евгений», разработанная группой российских специалистов, вплотную приблизилась к порогу «разумности», обманув судей в 29,2 % случаев.
Широко распространенный в Интернете тест CAPTCHA – это так называемый «обратный тест Тьюринга», в котором судьей, который должен отличить человеческий интеллект от искусственного, тоже является машина. Осталось только придумать тест Тьюринга, в котором машина будет отличать машину от машины, и мы достигнем полной автоматизации процесса тестирования.
Это новость от журнала ММ «Машины и механизмы». Не знаете такого? Приглашаем прямо сейчас познакомиться с этим удивительным журналом.