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