Компьютеры настолько прочно срослись с информатикой, что само название дисциплины кажется самоочевидным. Но значительная часть computer science прекрасно обходится без процессоров, памяти и программ. Теоретики десятилетиями исследуют вычисления как математический объект и порой вообще не работают с реальными машинами. Quanta Magazine решила разобраться, нужна ли науке о вычислениях техника, которая дала ей имя.
Спор далеко не новый. Один из самых известных специалистов по информатике Эдсгер Дейкстра любил сравнивать компьютеры с телескопами. По смыслу приписываемой ему фразы информатика относится к компьютерам примерно так же, как астрономия к телескопам. Машина служит инструментом, а сама наука занимается куда более фундаментальными вопросами.
История частично подтверждает такой взгляд. Математическую теорию вычислений начали создавать еще в 1930-х годах, до появления электронных компьютеров общего назначения. Алан Тьюринг в знаменитой работе 1937 года описал абстрактную машину с бесконечной лентой и набором простых правил. Тьюринг не пытался спроектировать будущий компьютер. Математика интересовал другой вопрос, связанный с пределами формальных вычислений и основаниями математики.
Позднее выяснилось, что машина Тьюринга математически эквивалентна другим моделям вычислений. Исследователи получили универсальный язык, позволяющий спрашивать не о конкретном процессоре или программе, а о принципиальных границах вычислимого. Какие задачи вообще можно решить алгоритмом. Какие решить невозможно. Сколько шагов потребуется для получения ответа.
Такой подход постепенно превратил информатику в необычный гибрид математики и инженерии. Профессор Университета Буффало Уильям Рапапорт предлагает свести дисциплину к двум вопросам. Что можно вычислить и как именно вычислить нужный результат. Первая половина почти полностью принадлежит математике. Вторая постоянно сталкивается с реальными ограничениями вычислительных систем.
Особенно ярко граница проявилась при развитии теории вычислительной сложности в конце 1960-х и начале 1970-х годов. Ученые заметили, что некоторые задачи компьютеры решают быстро, тогда как другие требуют огромного числа операций даже при сравнительно небольшом объеме входных данных. Разница не обязательно связана со скоростью процессора или талантом программиста. У математических задач существует собственная структура сложности. Исследование такой структуры со временем легло в основу современной криптографии и породило знаменитую проблему P против NP.
Теоретическая информатика ушла еще дальше от обычного представления о компьютерах. Работы по вычислительной сложности привели к новым представлениям о математическом доказательстве. Исследователи обнаружили интерактивные доказательства, а позднее разработали методы, позволяющие подтвердить истинность утверждения, не раскрывая сам секрет. Подобные идеи сегодня лежат в основе доказательств с нулевым разглашением.
Возникает парадокс. Многие фундаментальные вопросы можно было сформулировать задолго до появления электронных машин. Но математики попросту не задавали их. Теоретик Скотт Ааронсон считает, что часть подобных проблем могла появиться сотни лет назад. Причина задержки оказалась скорее исторической, чем математической. Реальные компьютеры показали, какие вопросы вообще стоит задавать.
Еще в XIX веке Чарльз Бэббидж приблизился к той же мысли, проектируя свою Аналитическую машину. Бэббидж задумался, каким способом вычислений машина сможет получить результат быстрее всего. Полноценная теория сложности появилась намного позже, когда исследователи получили настоящие компьютеры и начали сравнивать алгоритмы на практике.
Поэтому знаменитое сравнение Дейкстры работает лишь наполовину. Информатика действительно может существовать без физического компьютера, как теория чисел существует без калькулятора. Но реальные машины постоянно подбрасывают математике новые фундаментальные проблемы. Компьютеры в таком смысле похожи на телескопы гораздо сильнее, чем предполагала старая шутка. Астрономия не сводится к телескопам, однако без телескопов человечество знало бы о Вселенной несравнимо меньше.
История computer science показывает более общий механизм развития науки. Теория не всегда сначала рождает технологию. Иногда все происходит наоборот. Паровые машины заставили физиков задуматься о термодинамике, а компьютеры заставили математиков исследовать природу вычислений. Практическая задача может выглядеть банально, пока не выяснится, что за ней скрывается новая область фундаментальной науки.