На протяжении более 2000 лет великие инженеры, математики и ученые производили различные аналоговые компьютеры. Начиная от антикитерского механизма древности и заканчивая разностными машинами викторианского периода. Однако в 1930-х, 40-х и 50-х годах был большой всплеск активности, который перенес нас из аналоговой эпохи в цифровую.

Период между 1930 и 1960 годами можно рассматривать как разделительную линию в истории. 30-летний период, перевернувший с ног на голову более 2000 лет истории человечества. Это началось с разработки электромеханического компьютера и закончилось разработкой цифрового компьютера на основе транзисторов. Мир полностью изменился, и одним из людей, ответственных за это великое изменение, является Алан Тьюринг.

В 1936 году Тьюринг опубликовал статью под названием О вычислимых числах с приложением к проблеме Entscheidungsproblem. Статья опровергла Проблему принятия решения Дэвида Гильберта и Уильяма Аккермана, задачу, которая спрашивала, разрешима ли каждая проблема. Или, другими словами, можно показать, что оно истинно или ложно. Как описывает это профессор Мелани Митчелл.

Всегда ли существует определенная процедура, которая может решить, истинно ли утверждение?

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

Все проблемы могут быть закодированы как нули и единицы (двоичный код AKA), а затем можно следовать простому набору правил на основе считанных нулей и единиц. В простейшей форме человек мог читать нули и единицы с ленты и следовать правилам, и это была первоначальная мысль Тьюринга. Несмотря на свою неэффективность, эту систему можно использовать для решения любой вычислимой задачи.

Но чтобы показать, что не все проблемы вычислимы, и опровергнуть проблему принятия решения, Тьюринг использовал технику, называемую «доказательством от противного». Он начал с того, что заявил, что можно построить машину Тьюринга, которая могла бы вычислить, будет ли программа, получающая некоторый ввод, останавливаться или работать вечно. Затем он показал бы, что эта машина может привести к противоречию, поэтому не может существовать.

Эта идея, которую затронул Тьюринг, позже будет названа проблемой остановки. Сегодня разработчики программного обеспечения знают это как бесконечный цикл, и многие из них сталкиваются с этой проблемой при написании циклов или рекурсивных функций. Пример бесконечного цикла в C++ можно увидеть ниже, программе while() был предоставлен ввод true, поэтому он всегда будет выводить hello на консоль.

#include <iostream>
using namespace std;
int main() {
  while (true) {
    cout << "hello" << endl;
  }
}

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

Как утверждает Митчелл, это была новаторская работа как для математики, так и для компьютеров.

[Тьюринг] строго определил понятие «определенная процедура». Во-вторых, его определение в виде машин Тьюринга заложило основу для изобретения электронных программируемых компьютеров. В-третьих, он показал то, чего мало кто ожидал: существуют пределы того, что можно вычислить.

Затем машина Тьюринга привела к концепции полноты Тьюринга, которая стала эталоном для современных компьютеров и языков программирования. Полная машина Тьюринга — это просто машина или программа, которая может имитировать поведение любой машины Тьюринга. Проще говоря, это просто означает, что он может решить любую вычислимую задачу. Неизвестно на 100%, когда появилась первая машина Turing Complete. Некоторые утверждают, что это был Z3 Конрада Цузе в 1941 году, другие – Колосс Томми Флауэра в 1943 году, но все согласны с тем, что ENIAC, завершенный американцами в 1945 году, был завершен по Тьюрингу.

Тьюринг заложил основу для цифрового компьютера в 1930-х годах, опровергнув проблему принятия решений и описав машину Тьюринга. К концу 1950-х годов его глубокое понимание вычислений привело к созданию современного цифрового компьютера, который мы знаем сегодня. Трагически Тьюринг покончил жизнь самоубийством в 1954 году после того, как британское государство преследовало его из-за его сексуальной ориентации. К сожалению, он никогда не увидит чудеса современного мира, в создании которых он сыграл ключевую роль.

Полезные ресурсы: