Введение

История информатики началась задолго до формирования современной дисциплины, обычно проявляясь в виде математики или физики. Достижения предыдущих столетий предвосхищали ту область знаний, которую мы сегодня называем информатикой. Этот прогресс, от механических изобретений и математических теорий к современным компьютерным концепциям и машинам, привёл к развитию крупной академической области, значительному технологическому прогрессу в западном мире и созданию основы для масштабной мировой торговли и культуры.

Предыстория

Самым ранним известным инструментом для вычислений был абакус, разработанный в период между 2700 и 2300 годами до нашей эры в Шумере. Абакус шумеров состоял из таблицы последовательных столбцов, которые определяли последовательные порядки величины их шестидесятеричной системы счисления. Первоначально его использовали, рисуя линии в песке с использованием камешков. Абаки более современной конструкции до сих пор используются в качестве инструментов для вычислений, например, китайский абакус. В 5 веке до н.э. в древней Индии грамматик Панини сформулировал грамматику санскрита в 3959 правилах, известных как «Аштадхьяи», которые были высоко систематизированы и носили технический характер. Панини использовал метаправила, преобразования и рекурсии. Механизм Антикитеры считается ранним механическим аналоговым компьютером. Он был разработан для вычисления астрономических положений. Он был обнаружен в 1901 году в обломках корабля у острова Антикитера (Греция), между Китерой и Критом, и датируется приблизительно 100 годом до н.э., а также торкетум, созданный Джабиром ибн Афлахом. По словам Саймона Синга, мусульманские математики также внесли важный вклад в криптографию, например, разработали криптоанализ и частотный анализ благодаря Алькиндусу. Программируемые машины также были изобретены мусульманскими инженерами, такие как автоматический флейтист братьев Бану Муса.

Технологические артефакты аналогичной сложности появились в Европе в 14 веке с появлением механических астрономических часов. После того как Джон Непер открыл логарифмы для вычислительных целей в начале 17 века, последовал период значительного прогресса, достигнутого изобретателями и учеными в создании вычислительных инструментов. В 1623 году Вильгельм Шикард спроектировал вычислительную машину по заказу Иоганна Кеплера, которую он назвал «Вычислительные часы», но отказался от проекта, когда прототип, над которым он работал, был уничтожен пожаром в 1624 году. Около 1640 года Блез Паскаль, выдающийся французский математик, сконструировал механическое устройство для сложения, основанное на конструкции, описанной греческим математиком Героном Александрийским. Затем, в 1672 году, Готфрид Вильгельм Лейбниц изобрел «Счетную машину Лейбница», которую он завершил в 1694 году. В 1837 году Чарльз Бэббидж впервые описал свою Аналитическую машину, которая признана первым проектом современного компьютера. Аналитическая машина имела расширяемую память, арифметическое устройство и возможности логической обработки, способные интерпретировать язык программирования с циклами и условными переходами. Хотя она так и не была построена, ее конструкция была тщательно изучена и признана эквивалентной машине Тьюринга. Аналитическая машина имела бы объем памяти менее 1 килобайта и тактовую частоту менее 10 Герц. Для создания первых современных компьютеров потребовался значительный прогресс в математике и теории электроники.

Готфрид Вильгельм Лейбниц

В 1702 году Готфрид Вильгельм Лейбниц разработал логику в формальном, математическом смысле в своих трудах по двоичной системе счисления. Лейбниц упростил двоичную систему и сформулировал логические свойства, такие как конъюнкция, дизъюнкция, отрицание, тождество, включение и пустое множество. Он предвосхитил интерполяцию Лагранжа и алгоритмическую теорию информации. Его «Calculus Ratiocinator» предвосхитил аспекты универсальной машины Тьюринга. В 1961 году Норберт Винер предложил считать Лейбница покровителем кибернетики. Винер утверждал: «Действительно, общая идея вычислительной машины – это не что иное, как механизация «Calculus Ratiocinator» Лейбница». Но потребовалось более века, прежде чем Джордж Буль опубликовал свою булеву алгебру в 1854 году, представив полную систему, позволяющую математически моделировать вычислительные процессы. К тому времени были изобретены первые механические устройства, управляемые двоичным кодом. Промышленная революция способствовала механизации многих задач, в том числе ткачества. В 1801 году ткацкий станок Жозефа Мари Жаккарда управлялся перфокартами, где отверстие в карте обозначало двоичную единицу, а отсутствие отверстия – двоичный ноль. Станок Жаккарда был далек от компьютера, но он продемонстрировал, что машины могут управляться двоичными системами и хранить двоичную информацию. Два других изобретателя, Леонардо Торрес Кеведо и Ванневар Буш, также продолжили исследования, основанные на работе Бэббиджа. В своих «Эссе по автоматике» (1914) Торрес спроектировал аналитическую электромеханическую машину, управляемую программой только для чтения, и ввел понятие арифметики с плавающей запятой. В 1920 году, в честь 100-летия изобретения арифмометра, он представил в Париже электромеханический арифмометр, состоящий из арифметического устройства, подключенного к (возможно, удаленной) пишущей машинке, на которой можно было вводить команды и автоматически печатать результаты. В статье Буша «Инструментальный анализ» (1936) обсуждалось использование существующих машин IBM с перфокартами для реализации проекта Бэббиджа. В том же году он начал проект «Быстрая арифметическая машина» для изучения проблем создания электронного цифрового компьютера.

Чарльз Сандерс Пирс и электрические коммутационные схемы

В письме 1886 года Чарльз Сандерс Пирс описал, как логические операции могут выполняться электрическими коммутационными схемами. В 1880–1881 годах он показал, что только логических элементов NOR (или, альтернативно, только NAND) достаточно для реализации функций всех остальных логических элементов, однако эта работа оставалась неопубликованной до 1933 года. Первое опубликованное доказательство представил Генри М. Шеффер в 1913 году, поэтому логическую операцию NAND иногда называют штрихом Шеффера, а логический элемент NOR – стрелкой Пирса. Следовательно, эти элементы иногда называют универсальными логическими элементами. В конечном итоге вакуумные лампы заменили реле для выполнения логических операций. Модификация, предложенная Ли Де Форестом в 1907 году, диода Флеминга может быть использована в качестве логического элемента. Людвиг Витгенштейн представил версию 16-строчной таблицы истинности как предложение 5.101 в «Логико-философском трактате» (1921). Уолтер Боте, изобретатель схемы совпадений, получил часть Нобелевской премии по физике 1954 года за создание первого современного электронного элемента И в 1924 году. Конрад Цузе разработал и построил электромеханические логические элементы для своего компьютера Z1 (с 1935 по 1938 год). Вплоть до и в течение 1930-х годов инженеры-электрики могли создавать электронные схемы для решения математических и логических задач, но большинство из них делали это эмпирическим путем, без какой-либо теоретической основы. Это изменилось с развитием теории коммутационных схем в 1930-х годах. С 1934 по 1936 год Акира Накасима, Клод Шеннон и Виктор Шетаков опубликовали серию работ, показавших, что двухзначная булева алгебра может описывать работу коммутационных схем. Эта концепция – использование свойств электрических переключателей для выполнения логических операций – является базовой концепцией, лежащей в основе всех электронных цифровых компьютеров. Теория коммутационных схем предоставила математические основы и инструменты для проектирования цифровых систем практически во всех областях современных технологий.

Алан Тьюринг и машина Тьюринга

До 1920-х годов компьютерами (иногда компутерами) называли людей, выполнявших вычисления. Обычно ими руководил физик. Тысячи компьютеров были заняты в коммерческих, государственных и исследовательских учреждениях. Многие из этих людей, работавших в качестве человеческих компьютеров, были женщинами. Одни выполняли астрономические расчёты для календарей, другие – баллистические таблицы для военных нужд. После 1920-х годов выражение «вычислительная машина» стало относиться к любому устройству, выполнявшему работу человеческого компьютера, особенно в соответствии с эффективными методами, лежащими в основе тезиса Чёрча — Тьюринга. Тезис утверждает, что математический метод является эффективным, если его можно представить в виде списка инструкций, которые человеческий клерк может последовательно выполнять с помощью бумаги и карандаша столько, сколько потребуется, без проявления изобретательности или интуиции. Машины, работавшие с непрерывными значениями, стали известны как аналоговые. Они использовали механизмы, представлявшие непрерывные числовые величины, такие как угол поворота вала или разность электрических потенциалов. Цифровые машины, в отличие от аналоговых, могли отображать состояние числового значения и хранить каждую отдельную цифру. До изобретения более быстрых устройств памяти цифровые машины использовали дифференциальные анализаторы или реле. Фраза «вычислительная машина» постепенно уступила место просто «компьютеру» после конца 1940-х годов, с распространением электронной цифровой техники. Эти компьютеры могли выполнять вычисления, которые ранее выполняли люди. Поскольку значения, хранящиеся в цифровых машинах, не были привязаны к физическим свойствам, как в аналоговых устройствах, логический компьютер, основанный на цифровом оборудовании, мог выполнять всё, что можно было описать как «чисто механическое». Теоретическая машина Тьюринга, созданная Аланом Тьюрингом, – это гипотетическое устройство, разработанное для изучения свойств подобного оборудования. Математические основы современной информатики начал закладывать Курт Гёдель со своей теоремой о неполноте (1931). В этой теореме он показал, что существуют ограничения на то, что можно доказать или опровергнуть в рамках формальной системы. Это привело к работам Гёделя и других исследователей по определению и описанию этих формальных систем, включая такие понятия, как мю-рекурсивные функции и лямбда-определимые функции. В 1936 году Алан Тьюринг и Алонзо Чёрч независимо, а также совместно представили формализацию алгоритма, с ограничениями на то, что может быть вычислено, и «чисто механическую» модель вычислений. Это стало тезисом Чёрча — Тьюринга, гипотезой о природе механических вычислительных устройств, таких как электронные компьютеры. Тезис утверждает, что любое возможное вычисление может быть выполнено алгоритмом, работающим на компьютере, при условии, что доступно достаточно времени и памяти. Эти гипотетические машины были разработаны для формального математического определения того, что может быть вычислено, с учётом ограничений вычислительных возможностей. Если машина Тьюринга может выполнить задачу, она считается Тьюринг-вычислимой. Она помогла разработать три различных машины, включая ARC, SEC (Простой электронный компьютер) и APE(X)C.

Ранние компьютерные устройства

Первый в мире электронный цифровой компьютер, компьютер Атанасова–Берри, был построен на территории кампуса штата Айова с 1939 по 1942 год Джоном В. Атанасовым, профессором физики и математики, и Клиффордом Берри, аспирантом инженерного факультета. В 1941 году Конрад Цузе разработал первый в мире функциональный компьютер, управляемый программой, – Z3. В 1998 году было показано, что он является Тьюринг-полным по своей сути. Цузе также разработал вычислительную машину S2, которую считают первым компьютером для управления технологическими процессами. В 1941 году он основал одно из первых предприятий по производству компьютеров, выпустив Z4, который стал первым в мире коммерческим компьютером. В 1946 году он разработал первый язык программирования высокого уровня – Plankalkül. В 1948 году был завершен «Манчестер-Бэби» – первый в мире электронный цифровой компьютер, который выполнял программы, хранящиеся в его памяти, как и почти все современные компьютеры. Дизайн ACE, разработанный Тьюрингом, имел много общего с современными RISC-архитектурами и требовал высокоскоростной памяти примерно того же объема, что и у первых компьютеров Macintosh, что было огромным по меркам того времени. Хотя изобретение термина «баг» часто, но ошибочно приписывается Грейс Хоппер, будущему контр-адмиралу ВМС США, которая, как утверждается, зафиксировала «баг» 9 сентября 1945 года, большинство других свидетельств противоречат, по крайней мере, этим деталям. Согласно этим свидетельствам, фактической датой было 9 сентября 1947 года, когда операторы зарегистрировали этот «инцидент» вместе с насекомым и пометкой «Первый зафиксированный случай обнаружения ошибки» (подробности см. в статье «Ошибка программного обеспечения»).

Винер и кибернетика

Исходя из экспериментов с зенитными системами, интерпретировавшими радиолокационные изображения для обнаружения вражеских самолетов, Норберт Винер ввёл термин «кибернетика» от греческого слова, означающего «кормчий». В 1948 году он опубликовал книгу «Кибернетика», оказавшую влияние на развитие искусственного интеллекта. Винер также сопоставлял вычисления, вычислительную технику, устройства памяти и другие когнитивные особенности со своим анализом мозговых волн.

Джон фон Нейман и архитектура фон Неймана

В 1946 году была представлена модель компьютерной архитектуры, получившая название архитектура фон Неймана. Начиная с 1950 года, модель фон Неймана обеспечивала единообразие в последующих конструкциях компьютеров. Архитектура фон Неймана считалась новаторской, поскольку она предложила идею совместного использования машинным инструкциям и данным пространства памяти. Модель фон Неймана состоит из трех основных частей: арифметико-логического устройства (ALU), памяти и устройства обработки инструкций (IPU). В конструкции машины фон Неймана IPU передает адреса в память, а память, в свою очередь, направляет их обратно в IPU, если происходит выборка инструкции, или в ALU, если происходит выборка данных. 31 августа 1955 года был предложен исследовательский проект с участием Джона Маккарти, Марвина Л. Мински, Натаниэля Рочестера и Клода Э. Шеннона. Официальный проект стартовал в 1956 году и включал несколько важных направлений, которые, по мнению исследователей, помогут лучше понять структуру искусственного интеллекта. Идея Маккарти и его коллег, лежащая в основе автоматических компьютеров, заключалась в том, что если машина способна выполнить задачу, то это должно быть подтверждено компьютером путем создания программы для достижения желаемого результата. Они также пришли к выводу, что человеческий мозг слишком сложен для воспроизведения, причем не самими машинами, а программой. Знаний, необходимых для создания столь сложной программы, на тот момент еще не было. Суть заключалась в изучении того, как люди понимают свой язык и структуру построения предложений, придавая им различные значения и правила, и сопоставлении этого с машинным процессом. Компьютеры способны понимать информацию только на аппаратном уровне. Этот язык записан в двоичном коде (1 и 0), который должен быть представлен в определенном формате, задающем компьютеру набор правил для работы с конкретным оборудованием. Процесс, разработанный Мински, определял, как эти искусственные нейронные сети могут быть организованы для достижения характеристик, схожих с человеческим мозгом. Однако он смог получить лишь частичные результаты и нуждался в дальнейшем изучении этой идеи. Идея Маккарти и Шеннона заключалась в разработке метода использования сложных задач для определения и измерения эффективности машины с помощью математической теории и вычислений. Однако они получили лишь частичные результаты тестирования. Концепция самосовершенствования заключается в том, как машина может использовать самомодифицирующийся код для повышения своей интеллектуальности. Это позволило бы машине развивать интеллект и увеличивать скорость вычислений. Группа полагала, что сможет изучить это, если машина сможет улучшить процесс выполнения задачи в рамках абстрактной части их исследования. Группа считала, что исследования в этой области можно разбить на более мелкие группы, включающие сенсорную и другие формы информации об искусственном интеллекте. Абстракции в информатике могут относиться к математике и языкам программирования. Их представление о вычислительном творчестве заключалось в том, что программа или машина могут демонстрировать способы мышления, схожие с человеческими. Они хотели выяснить, способна ли машина взять неполную информацию и улучшить ее, дополняя недостающие детали, как это делает человеческий разум. Если бы машина смогла это сделать, им нужно было бы понять, как она определяет результат.