Пришло время устранить несправедливость и познакомиться, наконец, с отцом-основателем науки о компьютерах - Аланом Тьюрингом, а также с изобретённой им удивительной машиной, с которой на самом деле и следовало бы начать этот курс. Но уж как получилось.
Вспомните главу об игре Жизнь. В ней мы познакомились с "машиной Тьюринга", смоделированной с помощью двухмерного клеточного автомата. Тогда мы не стали разбираться ни с самой машиной, ни с её изобретателем. Сделаем это сейчас.
Великий английский математик Алан Метисон Тьюринг родился в 1912 году.
В школе Тьюринг был неуправляем, собственные идеи занимали его гораздо больше, чем то, что втолковывали учителя. Он ставил собственные химические опыты, которыми приводил учителей в изумление, изучал теорию относительности и читал статьи по квантовой механике.
Во время учёбы в Кембридже, где вольная обстановка позволяла таким гениям, как Тьюринг, дышать свободней, он начал интересоваться математической логикой и основаниями математики.
Широта интересов Тьюринга была огромна, и в 1935 году он закончил диссертацию, в которой доказал некоторые фундаментальные результаты теории вероятностей, а уже в следующем году он опубликовал работу с труднопроизносимым названием On Computable Numbers, with an application to the Entscheidungsproblem, в которой представил некую абстрактную машину (называемую теперь Машиной Тьюринга), с которой мы вскоре и познакомимся поближе.
Алан Тьюринг считается одним из отцов компьютерной науки потому, что в своей работе, задолго до появления настоящих, "железных" компьютеров, он заложил основные принципы знакомых нам современных компьютеров. В своей работе, кроме уже упомянутой машины, он доказал существование Универсальной Машины Тьюринга (её тоже назвали так, конечно, позже), которая "может совершать работу вместо любой другой узкоспециальной машины, то есть вычислять любой алгоритм, следуя соответствующим инструкциям на вставленной в неё ленте". Мы вернёмся к этому поистине фундаментальному результату после того, как познакомимся с обычной, не универсальной Машиной Тьюринга.
Сразу же после начала Второй Мировой войны Тьюринг начал работать в британском криптоаналитическом агентстве Bletchley Park, где ему и его команде удалось расшифровать перехваченные сообщения, сделанные с помощью германской шифровальной машины "Энигма". Сначала Тьюринг построил свою собственную машину - Bombe, которая с лёгкостью расшифровывала сообщения Энигмы, посылавшиеся Luftwaffe - немецкими военно-воздушными силами. Однако, немецкие морские войска использовали более совершенную Энигму, взломать коды которой было гораздо сложнее. И тем не менее в 41-м году Тьюринг разработал специальный статистический метод, который позволил победить и морскую Энигму. Эта работа спасла множество жизней британских моряков и, как говорят, во многом определила исход войны[1].
После войны сфера интересов Тьюринга ещё более расширилась и включила неврологию и психологию. В 1950 году он опубликовал работу под названием Computing machinery and intelligence, заложившую основы исследований по искусственному интеллекту. Именно здесь Тьюринг сформулировал знаменитый "Тест Тьюринга", который по его предположению мог бы позволить определить наличие у компьютера искусственного интеллекта[2].
Многочисленные заслуги Алана Тьюринга перед человечеством несомненны, но более всего его имя всё-таки ассоциируется с одноимённой машиной.
Что же это за машина и зачем она нужна ?
Машина Тьюринга необычайно проста, причём в её простоте и заключается её сила (в чём именно заключается эта сила, мы увидим позже). Машина состоит из нескольких элементарных частей:
- бесконечная лента[3], поделённая на клетки, в каждой из которых может поместиться один из символов некоего данного алфавита.
- сам алфавит, который, в принципе, может быть любым. В простейшем случае - это алфавит, состоящий из трёх символов - 0, 1 и какой-либо разделительный симовол, например #. Всем известно, что любую информацию можно представить в так называемом двоичном (или бинарном) виде, с помощью нулей и единиц. Разделительный символ поможет нам узнавать отдельные слова или числа.
- считывающе-записывающее устройство. Это устройство в любой данный момент времени находится над одной из клеток бесконечной ленты. Оно может распознать символ, записанный в этой клетке, может записать на его место какой-то другой символ (например, заменить 0 на 1), и, кроме того, это устройство обладает способностью передвигаться по ленте вправо или влево - одна клетка за один шаг.
- и, наконец, составляющая машины Тьюринга, которую в наше время мы бы назвали software, или попросту программа, управляющая машиной.
Прграмма эта может в принципе иметь любой вид, но мы, для удобства, будем изображать её в виде таблицы. Для того, чтобы понять, как устроена таблица (программа), управляющая машиной Тьюринга, нам нужно познакомиться с понятием состояния. Машина Тьюринга в любой момент времени находится в одном из состояний. Состояния эти определены в программе, которая управляет считывающим устройством. Состояния машины определяют, какой символ алфавита должен быть вписан в текущую клетку на ленте, и в какую сторону должно передвинуться (если должно) считывающее устройство.
Таблица машины Тьюринга представляет собой описание всех возможных состояний, причём каждое из них должно описывать действия считывающего устройства в зависимости от каждого из возможных символов в текущей клетке.
Для примера рассмотрим часть таблицы (программы) некоей машины Тьюринга:
Эта таблица означает следующее:
1. если под считывающим устройством на ленте записан символ 0, то:
- оставить 0 без изменений;
- сдвинуться на одну клетку влево;
- остаться в состоянии А;
2. если под считывающим устройством на ленте записан символ 1, то:
- изменить 1 на 0;
- сдвинуться на одну клетку вправо;
- перейти в состояние В;
3. если под считывающим устройством на ленте записан символ #, то:
- изменить # на 1;
- перейти в состояние В;
Естественно, таблица всегда должна содержать полный список возможных состояний. Так, если мы забудем строчку с символом #, машина просто не будет знать, что делать, встретив на ленте этот символ (и находясь в состоянии А).
В следующей части мы подробно разберём принцип работы Машины Тьюринга на примере программы, которая - готовы ли вы к сюрпризу? - прибавляет единицу к заданному числу.
[1] Здесь необходимо восстановить историческую справедливость и упомянуть, что Тьюринг не смог бы расшифровать коды Энигмы без предварительных результатов польского математика Марьяна Реевского, которому удалось не расшифровать, но понять механизм работы Энигмы ещё в 1932 году.
[2] Тест Тьюринга проводится следующим образом:
Человек, проводящий тест, сидит в комнате, соединённый с помощью компьютерного терминала с двумя другими комнатами. В одной из них находится человек, во второй - компьютер, претендующий на звание "мыслящего". Проводящий тест может задавать любые вопросы двум своим собеседникам и в конце концов должен определить, кто из них компьютер. Если он не может этого определить, компьютер объявляется мыслящим.
[3] Не забывайте, что машина - воображаемая, а стало быть и лента может быть бесконечной.