Представьте себе 1936 год. Европа на пороге войны, но в тихих кабинетах университетов происходит интеллектуальная революция, которая изменит мир сильнее любых армий. Молодой английский математик Алан Тьюринг задаётся вопросом, который кажется чисто философским: что такое вычисление? Можно ли формально описать, что значит «решить задачу»? Тьюринг не знает, что его размышления заложат фундамент компьютерной эры. Он придумывает воображаемую машину — бесконечную ленту с символами и считывающую головку, которая может двигаться влево-вправо, читать символы и записывать новые...

В 1936 году англичанин Алан Тьюринг и американец Алонзо Черч, оба — математики, официально предложили алгоритм, описывающий способ числовой обработки информации, и представили модель развития компьютерной технологии. Тезис, известный под названием тезиса Черча-Тьюринга, по существу, утверждает, что если функция поддается вычислению, то ее можно вычислить с помощью компьютера. Теория обращается к основным свойствам вычислительных устройств, таких как электронные компьютеры, и утверждает, что любое...