Тогда правило для начала работы выглядит так: если в состоянии 0 мы читаем 0 – перейти в состояние 0, написать 0 и перейти вправо.
Это означает, что если вначале машина видит 0 (находясь в состоянии 0), она остаётся в состоянии 0, не изменяет запись 0 на ленте и переходит на шаг вправо. Если следующий знак – опять 0, повторяется то же самое: машина остаётся в состоянии 0, не делает отметок на ленте и передвигается ещё на шаг вправо.
Всё это повторяется с каждым тиканьем часов, пока наконец машина не достигнет первой единицы на ленте. Теперь требуется правило, объясняющее, что делать, когда процессор читает 1 в состоянии 0. Простейшим правилом будет: оставаться в состоянии 0, записать 1, перейти на шаг вправо и остановиться. Теперь слева от машины будет записана единица, и это будет результат вычисления.
Этот алгоритм можно описать как «печатать 1, если входные данные корректны», где «корректны» означает «содержат по меньшей мере одну единицу». Если бы на момент начала работы справа от управляющего устройства не было ни одной единицы, она бы никогда не остановилась, а продолжала бы движение в вечном и бесплодном поиске единицы. Такое может произойти и с настоящим компьютером: программа может «зациклиться», и в конце концов компьютер сломается.
К сожалению, такая возможность – неотъемлемое свойство и машины Тьюринга, и реальных компьютеров. Однако этого легко избежать, если изначально указать, что среди «корректных» входных данных должна быть по меньшей мере одна единица, так, чтобы первое правило не могло применяться до бесконечности.
Тьюринг также математически показал, что даже машина Тьюринга не может решить все задачи! Иными словами, некоторые задачи в математике не решаются с помощью вычислительной техники – то есть математиков пока нельзя заменить машинами.
Любое возможное вычисление
Если есть достаточно времени и есть возможность записать на ленте ввода нужное число единиц, то выполнимо любое механическое действие с целыми числами, какое только можно придумать. Для этого требуется дать машине Тьюринга входное число справа от машины, запустить часы, дождаться остановки – и прочесть ответ слева от машины. К таким действиям относится любой арифметический расчёт, какой может произвести человек с помощью ручки и бумаги. Алан Тьюринг предложил такое определение вычислимого: вычислимо то, что может вычислить машина Тьюринга. Удивительно, но спустя примерно 80 лет это определение по-прежнему считается верным: все известные компьютеры могут выполнять вычисления только в пределах возможностей машины Тьюринга.
Эрик ахнул. Она явно не предупредила его о своих намерениях.
– Нет, вы не можете… – начал он.
– Очень даже могу, – твёрдо сказала Берил. – Я дарю её вашему математическому факультету. Вы, с вашими работами по квантовым компьютерам, – самый подходящий человек для такого подарка. Так что лучшее место для неё и придумать трудно.
– Что такое квантовый компьютер? – насторожился Джордж. Для него это была новость. Он давно обратил внимание на то, что Эрик в последнее время стал очень скрытен. На вопросы о том, над чем он сейчас работает, выдающийся учёный отвечал туманно и уклончиво.
Однако сегодня Эрик оказался существенно говорливее, чем обычно.
– Это очередной прорыв, – ответил он Джорджу. – Уже произошла цифровая революция в мире информации, а теперь мы стоим на пороге квантовой революции. Если мы сумеем создать квантовый компьютер – и не только создать, но и управлять им, что в данный момент кажется чрезвычайно сложным, – то сможем делать многое из того, что при нынешнем уровне компьютерных технологий выглядит совершенно непредставимым.
– Например? – спросил Джордж.
– С помощью квантового компьютера можно взломать любой код – на Земле не существует системы ограничения доступа, которая могла бы его остановить! – сказал Эрик, сияя. – И тогда мы сможем делать просто невероятные вещи в области обработки данных, в медицине, физике, машиностроении, математике. Это будет очередной гигантский прорыв в науке.
– Но при чём тут «Энигма»? – спросил Джордж.
– При том, – ответила Берил, – что «Энигма» – предшественница множества поразительных технологий. И важно, что «Энигма» на самом деле существует и доказала свою действенность. А квантовый компьютер на данный момент ещё не действует, поскольку не существует.