Создатели аналоговых компьютеров подошли к решению проблемы путем постепенного снижения требований (то есть позволяли решать только такие задачи, в которых допустима небольшая погрешность), и, если ограничиваться определенными вычислениями, эти компьютеры могли быть полезными. С другой стороны, цифровые компьютеры нуждаются в постоянном обмене информацией — не только между компьютерами, но и внутри самого компьютера. Это обмен информацией между модулем памяти и центральным процессором. Внутри центрального процессора осуществляется связь между регистрами и вычислительными регистрами. И даже в вычислительных регистрах происходит обмен между битовыми регистрами. Таким образом, обмен информацией идет буквально на всех уровнях. Если учесть, что количество ошибок быстро возрастает с усилением информационного обмена и что ошибка в одном байте информации может нарушить весь процесс, цифровые вычислительные методы, как казалось, были обречены на провал.
Таково оставалось общественное мнение до тех пор, пока американский математик Клод Шеннон (1916–2001) не показал, каким образом можно достичь достаточно точной передачи информации с помощью самых ненадежных каналов передачи. В своей всемирно известной статье «Математическая теория связи» (A Mathematical Theory of Communication), опубликованной в журнале Bell System Technical Journal в июле и октябре 1948 г., и, в частности, в теореме о пропускной способности канала Шеннон постулировал, что с помощью канала с любым уровнем шума (ниже 50 %, поскольку такой канал передает только шум) можно передавать сообщение с любой точностью. Другими словами, число ошибок может составлять один бит из n битов даже при сколь угодно большом значении n. Например, в предельном случае, если у вас есть канал, безошибочно передающий информацию лишь 51 % времени (то есть бит правильной информации передается лишь немного чаще, чем бит неправильной информации), вы тем не менее можете передавать сообщения таким образом, что ошибка будет лишь в одном бите из миллиона или в одном бите из триллиона или из триллиона триллионов бит.
Как же это возможно? Ответ заключается в избыточности информации. Сейчас это кажется очевидным, но тогда дело обстояло иначе. Если, к примеру, я передаю каждый бит информации три раза, надежность результата станет значительно выше. Если этого недостаточно, нужно просто повышать степень избыточности до тех пор, пока не будет достигнут приемлемый результат. Повтор информации — простейший путь получения желаемой точности передачи информации по каналу с высоким уровнем шума, но не самый эффективный. В статье Шеннона, с которой началось развитие теории коммуникации, были предложены оптимальные методы определения ошибок и коррекционные коды, позволяющие достичь любой точности передачи информации с помощью любого направленного канала связи.
Читатели старшего поколения наверняка помнят телефонные модемы, проводившие информацию по шумным аналоговым телефонным линиям. Такая связь сопровождалась шипением, свистом и многими другими помехами, но при этом позволяла передавать цифровые сообщения с очень высокой точностью — в соответствии с теоремой Шеннона о зашумленном канале. Та же проблема и такое же решение существуют для цифровой памяти. Почему, по вашему мнению, программные диски, CD и DVD продолжают работать даже при появлении царапин или после падения на пол? Еще раз скажем спасибо Шеннону.
Вычислительный процесс состоит из трех элементов: коммуникации (которая, как я подчеркнул, осуществляется как внутри компьютера, так и между компьютерами), памяти и логических вентилей (производящих арифметические и логические действия). Точность логических вентилей тоже можно сделать сколь угодно высокой с помощью определения ошибок и коррекционных кодов. Благодаря теореме и теории Шеннона мы можем без помех управлять большими массивами сложных цифровых данных и алгоритмов. Важно отметить, что головной мозг тоже использует принцип Шеннона, хотя эволюция человеческого мозга произошла задолго до появления мозга самого Шеннона! Как мы видели, большинство образов или идей (идея — тоже образ) хранится в мозге в избыточном количестве. Основной смысл избыточности образов заключается в преодолении ненадежности цепей нейронов.
Второй важный принцип в основе теории информации я уже упоминал — это универсальность вычислительных методов. В 1936 г. Алан Тьюринг описал «машину Тьюринга», которая представляет собой не реальный механизм, а еще один мысленный эксперимент. Этот абстрактный компьютер состоит из бесконечно длинной ленты памяти, в ячейках которой располагаются цифры 1 или 0. Эта информация служит для машины входным сигналом, и машина за один раз прочитывает информацию в одной ячейке. Кроме того, машина снабжена таблицей правил (в частности, подчиняется принципу хранимой программы), представленных в виде пронумерованных утверждений. Каждое правило определяет одно действие, если в текущей ячейке расположена цифра 0, и другое, если в текущей ячейке цифра 1. К возможным действиям относится написание на ленте 0 или 1, перемещение ленты на одну ячейку влево или вправо или остановка. Каждое состояние определяет следующее состояние машины.
Блок-диаграмма машины Тьюринга, состоящей из считывающей и записывающей головки и внутренней программы, осуществляющей переходы между состояниями.
Входной сигнал задается информацией на ленте. Программа работает, а когда алгоритм выполнен, машина останавливается и выходные данные оказываются отпечатанными на ленте. Заметим, что, хотя теоретически лента имеет бесконечную длину, любая реальная программа, не попадающая в бесконечный цикл, использует лишь ограниченную часть ленты, так что, если мы возьмем ленту конечного размера, машина по-прежнему сможет решать некий набор задач.
Схема машины Тьюринга кажется простой — так сделал ее создатель. Он хотел, чтобы его машина была максимально простой (но не проще, если перефразировать Эйнштейна[121]). В результате работ Тьюринга и его бывшего учителя Алонзо Черча был сформулирован так называемый тезис Черча — Тьюринга: если некая функция не может быть вычислена машиной Тьюринга, она не может быть вычислена никакой другой машиной, подчиняющейся законам природы. Хотя машина Тьюринга выполняет лишь несколько команд и обрабатывает за один раз только один бит информации, она может решить любую задачу, которую способен решить любой другой компьютер. Иными словами, любая машина, эквивалентная машине Тьюринга, может вычислить любой алгоритм (решить любую задачу, которую мы в состоянии сформулировать).
В «строгой» формулировке тезиса Черча — Тьюринга постулируется эквивалентность между тем, что и как думает человек, и тем, что может рассчитать машина. Основная идея заключается в том, что человеческий мозг подчиняется законам природы и поэтому его способность обрабатывать информацию не может превышать аналогичную способность машины (в том числе машины Тьюринга).
Безусловно, статья Тьюринга 1936 г. заложила теоретические основы информатики, но важно отметить, что на работу Тьюринга большое влияние оказала лекция венгерско-американского математика Джона фон Неймана (1903–1957), которую он прочел в Кембридже в 1935 г. Тьюринг использовал в своей машине концепцию фон Неймана о хранимой программе[122]. Верно и то, что на фон Неймана оказала влияние статья Тьюринга, где элегантным образом изложены принципы информатики; в конце 1930-х и в начале 1940-х гг. фон Нейман рекомендовал прочесть эту статью всем своим коллегам[123].
В той же статье Тьюринг поведал о другом неожиданном открытии, касающемся неразрешимых задач. Неразрешимые задачи — это те, что хорошо описываются единственным решением (которое, как можно показать, существует), но (как тоже можно показать) не могут быть решены никакой машиной Тьюринга (то есть вообще никакой машиной). Представление о существовании таких задач в корне противоречит сформировавшейся к началу XX в. догме о том, что все проблемы, которые можно сформулировать, являются решаемыми. Тьюринг показал, что число неразрешимых задач не меньше числа разрешимых задач. В 1931 г. к такому же выводу пришел Курт Гедель, сформулировавший «теорему о неполноте». Такая странная ситуация: мы можем сформулировать задачу, можем доказать, что у нее существует единственное решение, но при этом знаем, что никогда не сможем это решение найти.
Тьюринг показал, что вычислительные машины действуют на основании очень простого механизма. Поскольку машина Тьюринга (и, следовательно, любой компьютер) может определять свою дальнейшую функцию на основе полученных ею ранее результатов, она способна принимать решения и создавать иерархические информационные структуры любой сложности.
