Теория вычислимости
Что можно вычислить алгоритмически? Машина Тьюринга (1936): универсальная модель вычислений. Тезис Чёрча-Тьюринга: всё интуитивно вычислимое = тьюринг-вычислимое. Неразрешимость: проблема остановки (Halting problem). Рекурсивные и рекурсивно перечислимые множества.
Теория вычислимости
Машина Тьюринга
Абстрактная вычислительная модель: бесконечная лента, головка чтения/записи, набор состояний. Алан Тьюринг (1936). Определяет границы вычислимого.
Тезис Чёрча-Тьюринга
Всё, что интуитивно вычислимо, вычислимо на машине Тьюринга. Не теорема, а гипотеза. Лямбда-исчисление Чёрча (1936) = машина Тьюринга по мощности.