Машина Тьюринга (1936)
24-летний британский математик Алан Тьюринг публикует фундаментальную работу, где определяет абстрактную модель вычислений: бесконечную ленту, головку чтения/записи и конечный набор состояний. Такая машина способна моделировать любой алгоритм.
Проблема разрешимости
Тьюринг даёт отрицательный ответ на Entscheidungsproblem Давида Гильберта: существуют математические функции и задачи, для которых нет общего механического метода решения, включая проблему остановки. Алонзо Чёрч независимо получает эквивалентный результат.
Значение
Тезис Чёрча-Тьюринга утверждает, что любая эффективно вычислимая функция может быть вычислена машиной Тьюринга. Эта модель лежит в основе теории компиляторов, вычислительной сложности и искусственного интеллекта.