В 1936 году англичанин Алан Тьюринг и американец Алонзо Черч, оба — математики, официально предложили алгоритм, описывающий способ числовой обработки информации, и представили модель развития компьютерной технологии. Тезис, известный под названием тезиса Черча-Тьюринга, по существу, утверждает, что если функция поддается вычислению, то ее можно вычислить с помощью компьютера. Теория обращается к основным свойствам вычислительных устройств, таких как электронные компьютеры, и утверждает, что любое возможное вычисление может быть произведено по известному алгоритму на компьютере, при условии, что тот обладает достаточной скоростью и объемом памяти.
Машина Тьюринга, абстрактное устройство, разработанное вслед за данным тезисом, снабжена бесконечно длинной лентой и головкой, способной двигаться вдоль ленты, считывая нанесенные на ней символы и меняя по пути их значение, опираясь на таблицу правил. Несмотря на простоту всей теории, машина Тьюринга может быть адаптирована для воспроизведения логики любого компьютерного алгоритма: особенно она эффективна для описания действий центрального процессора, находящегося внутри компьютера. Работающие в данной области ученые используют машину Тьюринга для определения пределов вычислительной мощности.
Ограничения, однако, существуют и для самой этой теории. Есть, к примеру, проблемы, с которыми не может справиться даже машина Тьюринга, к тому же некоторые модели компьютеров способны проводить вычисления быстрее, чем она сама. Кроме того, машина Тьюринга не очень хорошо моделирует параллельные вычисления — то есть такие вычисления, которые проводятся одновременно и потенциально могут взаимодействовать друг с другом.
Кроме машины британский математик, логик и криптоаналитик Алан Тьюринг во время Второй мировой войны разработал технику дешифровки, работая в Национальная физической лаборатории, создал Автоматическую вычислительную машину, а в конце жизни заинтересовался математической биологией, которая занимается математическим представлением, решением медицинских задач и моделированием биологических процессов.
Тьюрингу, однако, пришлось столкнуться с проблемами личного плана — за свою гомосексуальность он был осужден в уголовном порядке и в 1952 году подвергся химической кастрации. В 1954 году покончил жизнь самоубийством. В сентябре 2009 года премьер-министр Великобритании Гордон Браун принес публичные извинения за то, как когда-то обошлись с великим ученым
