Почему Тьюринг открыл компьютерную эру?23  июня  человечество отметило  100-летие  одного из самых знаменитых математиков XX  века,  Алана Мэдисона Тьюринга. О том, почему его  считают  одним из «отцов» информационной эры, не только  разительно изменившей определенные грани  человеческой цивилизации, но и подвергающей сомнению  отдельные  принципы, на которых она испокон  века основывалась,  рассказывает Юрий Ревич.

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

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

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

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

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

1. Если в текущей ячейке записан 0, то выполнить команду 2, иначе (если 1) выполнить команду 3.

2. Записать 1 и перейти к команде 4.

3. Записать 0 и перейти к команде 4.

4. Сдвинуть головку вправо на одну ячейку и перейти к команде 1.

Программа закончится, когда очередная ячейка окажется пустой.

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

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

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

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

Впрочем, конечно же Тьюринг не закрыл направление ИИ – его выводы (как и остальных математиков, в частности, Геделя, Черча, Поста и др., работавших в том же направлении) касались лишь существования алгоритмов в общем случае. Однако никто не опровергал возможности применять компьютеры к конкретным случаям моделирования чисто человеческих задач. Тьюринг сам же и стал основоположником обновленного ИИ, впервые сделав попытку в работе 1950 г. «Вычислительные машины и интеллект» ответить на вопрос «может ли машина мыслить?» с точки зрения рационально рассуждающего математика. Появившийся в результате «тест Тьюринга» обсуждается до сих пор. Он даже стал основой для конкурса Лебнера — ежегодного соревнования программ «искусственного интеллекта». Стоит отметить, что пока еще никто не удостоился на нем высшей награды, а вот бронзовая медаль и премия в 2-3 тыс. долл. исправно вручаются каждый год.

В принципе, не возникает сомнений в том, что те задачи ИИ, которые можно представить в математическом виде, рано или поздно будут решены. Вполне вероятно, что для этого потребуется радикально обновить аппаратную базу, далеко выйдя за пределы прогнозировавшегося в 1950 г. Тьюрингом объема памяти в 1010 бит (чуть больше 1 Гбайт). Какая вычислительную мощность, для этого потребуется, можно представить на примере решения следующей задачи. Компьютер «Ватсон», выигравший в 2011 г. американскую телевикторину Jeopardy (в России эта программа называется «Своя игра»), по вычислительной мощности входит в первую-вторую сотню самых производительных суперкомпьютеров мира. Естественно, его научили «понимать» запросы на естественном языке практически без ограничений, распознавать юмор и учитывать социокультурный контекст (что очень важно, например, в случае перевода с одного языка на другой). Но даже довольно ограниченный искусственный интеллект в рамках такой определенной задачи потребовал почти 3000 процессорных ядер и 16 Тбайт памяти — и к тому же пришлось потратить около четырех лет на разработку этого уникального программного обеспечения.

Купить номер с этой статьей в PDF
2265