Книга Эта странная математика. На краю бесконечности и за ним - Дэвид Дарлинг

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

Во время учебы в Кембридже Тьюринг прослушал курс логики, из которого он узнал об Entscheidungsproblem. Убежденный в неправоте Гильберта, он решил посвятить этой проблеме отдельную научную работу. Тьюринг считал, что алгоритм, позволяющий определить, возможно ли доказать конкретное математическое утверждение, существует не всегда. Для работы над проблемой разрешимости ему требовался способ реализации алгоритмов: некое идеализированное устройство, умеющее выполнить любой заданный ему логический набор команд. Таким устройством стала придуманная им воображаемая “a-машина” (где буква а означала “автоматическая”), которая вскоре получила название “машина Тьюринга”, – чистая абстракция, он даже не предполагал воплощать ее в реальности. Конструкция ее была нарочито примитивной, а работала бы такая машина мучительно медленно. Она изначально создавалась исключительно как упрощенная до предела математическая модель вычислительной машины.

Машина Тьюринга состоит из бесконечно длинной ленты, разделенной на ячейки, каждая из которых может быть пустой или содержать 1 либо 0, и головки чтения-записи. Головка считывает по одной ячейке за шаг и выполняет определенное действие в зависимости от содержимого ячейки, внутреннего состояния головки и текущей команды в ее протоколе или программе. Команда может иметь, например, следующий вид: “Если вы находитесь в состоянии 18 и обозреваемая ячейка содержит 0, то замените его на 1, передвиньте ленту на одну ячейку влево и переключитесь в состояние 25”.

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

Простой пример: прибавление к цепочке из n единиц еще одной, или, другими словами, превращение n в n + 1. Входные данные в этом случае – последовательность единиц и за ней пустая ячейка либо, если n = 0, просто пустая ячейка. Головке дается первая команда: перейти к первой непустой ячейке – или, если известно, что на ленте нет вообще никаких данных, начать с любой ячейки – и считать ее содержимое. В случае, если в ячейке стоит 1, дается команда оставить ее как есть и перейти на одну ячейку вправо, не переключаясь в другое состояние; если же ячейка пустая, дается команда записать в ней 1 и остановиться. Дописав к цепочке цифр единицу, головка может, в зависимости от полученной команды, либо остановиться, либо вернуться в исходную позицию – например, для того чтобы начать процесс заново и дописать к цепочке еще одну единицу. Как вариант, после размещения головки над последней в цепочке единицей может быть введено какое-либо иное состояние, после чего головка начнет выполнять новый набор команд.

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

Затем Тьюринг создал в своем воображении особый вид вычислительной машины, известный сегодня под названием “универсальная машина Тьюринга”. Теоретически она была способна выполнять любую программу. Лента ее разделена на две части: на одной закодирована программа, на другой содержатся входные данные. Головка чтения-записи универсальной машины Тьюринга может перемещаться между этими частями и выполнять над входными данными операции в соответствии с командами, записанными в программе. Устройство предельно просто: бесконечно длинная лента, на которой содержится как программа, которую следует выполнить, так и входные и выходные данные, плюс головка чтения-записи. Машина может выполнять всего шесть простых операций: считывание, запись, перемещение влево, вправо, изменение состояния и остановка. Но, несмотря на эту простоту, возможности универсальной машины Тьюринга поражают воображение.

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

Изобретение универсальной машины Тьюринга привело к возникновению такого понятия, как эмуляция. Говорят, что один компьютер способен эмулировать некий другой, если он может выполнять программу (называемую эмулятором), которая фактически превращает его в этот другой компьютер. Например, компьютер, работающий под управлением операционной системы Mac OS, может выполнить программу, которая заставит его вести себя так, как если бы на нем была установлена система Windows, – правда, на это требуется много оперативной памяти, а обработка данных происходит медленно. Если подобная эмуляция возможна, два компьютера считаются математически эквивалентными.

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

По оригинальному описанию Тьюринга был даже сконструирован целый ряд реальных машин – в основном в качестве экспериментов по проектированию или для демонстрации работы простейших вычислительных устройств. Несколько машин было построено из деталей LEGO, в том числе одна – из конструктора LEGO Mindstorms NXT для создания программируемого робота. А вот рабочая модель, созданная изобретателем из штата Висконсин Майком Дэйви, напротив, “воплощает в себе классические эстетичность и функциональность описанной Тьюрингом машины” и сейчас находится в постоянной экспозиции Музея истории компьютеров в городе Маунтин-Вью (штат Калифорния).