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