Аналогичная проблема и аналогичное решение существуют и для цифровой памяти. Вы когда-нибудь задумывались, почему CD, DVD и программные диски продолжают работать даже после того, как упали на пол или были поцарапаны? Этим мы тоже обязаны Шеннону. Процесс вычислений состоит из трех элементов: связи (которая, как я уже говорил, имеет место как внутри, так и между машинами), памяти и логических вентилей (которые выполняют арифметические и логические функции). Точность логических вентилей можно сделать произвольно высокой с помощью особых кодов для обнаружения и исправления ошибок. Именно благодаря теореме Шеннона мы можем обрабатывать большие и сложные цифровые данные, используя для этого достаточно длинные алгоритмы.
Вторая важная идея, на которую опирается наш информационный век, – универсальность машинных вычислений. В 1936 году Алан Тьюринг описал «машину Тьюринга» – абстрактную вычислительную машину, которая состоит из бесконечно длинной ленты, разделенной на клетки с цифрами 1 или 0. Машина считывает одну клетку за другой и содержит набор правил в виде пронумерованных состояний, фактически представляющих собой хранимую в памяти программу. Каждое правило предписывает машине совершить одно действие, если в считываемой клетке стоит 0, и другое действие, если в считываемой клетке стоит 1. Возможные действия включают запись 0 или 1, перемещение ленты на одну клетку вправо или влево, остановку ленты. Каждое состояние содержит номер следующего состояния, в которое должна перейти машина. Завершив алгоритм, машина останавливается; выход процесса остается на ленте. Хотя лента теоретически бесконечна, любая программа (которая не подразумевает бесконечный цикл) использует конечную часть ленты; следовательно, если мы ограничимся конечной памятью, машина по-прежнему сможет решать широкий круг задач.
В машине Тьюринга нет ничего сложного, верно? На самом деле именно этого и добивался ученый. Он хотел, чтобы его машина была максимально простой (но не проще, перефразируя Эйнштейна). Позже Тьюринг и его бывший учитель, Алонзо Черч сформулировали тезис Черча – Тьюринга, согласно которому задача, которая не может быть решена машиной Тьюринга, не может быть решена никакой другой машиной. Хотя собственно машина Тьюринга способна выполнять крайне ограниченное количество команд и одновременно обрабатывает всего один бит, она может вычислить все, что может вычислить любая вычислительная машина.
Строгие интерпретации тезиса Черча – Тьюринга предполагают принципиальную эквивалентность того, что человек может думать или знать, и того, что может быть вычислено машиной. Основная идея заключается в том, что человеческий мозг подчиняется естественным законам; следовательно, его способность обрабатывать информацию не может превосходить таковую у машины (и соответственно у машины Тьюринга).
В своей статье Тьюринг заложил теоретические основы машинных вычислений. Хотя это целиком и полностью его заслуга, важно отметить, что большое влияние на него оказала лекция, прочитанная Джоном фон Нейманом в 1935 году в Кембридже (Англия). Лекция была посвящена идее программы, которую можно хранить в памяти – концепция, позднее воплощенная в машине Тьюринга. На фон Неймана в свою очередь произвела глубочайшее впечатление статья Тьюринга 1936 года, где были изложены принципы машинных вычислений и которую в конце 1930-х – начале 1940-х годов он включил в список обязательной литературы, составленный для своих коллег.
В той же работе Тьюринг сообщает о другом неожиданном открытии, а именно – о проблеме неразрешимых задач. Неразрешимые задачи – это хорошо описанные задачи с однозначным ответом, который, однако, не может быть вычислен на машине Тьюринга (т. е. на любой машине). Это противоречит постулату XIX века, гласящему, что все задачи, которые могут быть описаны, в конечном счете будут решены. Тьюринг показал, что неразрешимых задач столько же, сколько и разрешимых. В своей «Теореме о неполноте» 1931 года Курт Гедель приходит к аналогичному выводу. Таким образом мы оказываемся в странной ситуации: с одной стороны, мы можем описать задачу и доказать, что однозначный ответ существует, а с другой – знаем, что ответ никогда не будет найден.
Гораздо больше можно сказать о философском значении работ Тьюринга, Черча и Геделя, однако в рамках данного предисловия достаточно отметить следующее. Тьюринг показал, что в основе всех машинных вычислений лежит очень простой механизм. Поскольку машина Тьюринга (и, следовательно, любая вычислительная машина) способна определять дальнейший образ действий, исходя из результатов предыдущих операций, она способна принимать решения и моделировать произвольно сложные иерархии данных.