Универсальная машина

Одно из первых строгих определений понятия алгоритма предложил Курт Гёдель. Опираясь на свое определение, в 1931 году он доказал существование алгоритмически неразрешимых математических проблем, т. е. таких проблем, для которых отсутствуют алгоритмы их решения. Для математиков это было настоящим потрясением, поскольку говорило о невыполнимости программы Гильберта и разрушало мечту о достижении абсолютной строгости в математике.

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

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

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

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

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

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

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

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

Современный человек, хоть немного знакомый с программированием, да и просто с компьютерами, может воскликнуть: но почему математики не догадались саму программу тоже кодировать строкой символов и записывать на входную ленту?! К счастью, они догадались, иначе компьютеров не было бы до сих пор, но догадаться было заметно труднее, чем это может показаться сейчас, когда такая возможность широко известна и ее надо не открывать, а лишь обратить на нее внимание.

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

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

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

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

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

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

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

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