Створення методу λ-числення
У 1936 році Алонсо Черч створив метод визначення, званих λ-обчисленням. Він був пов’язаний з натуральними числами. Всередині λ-числення вчений визначив їх кодування. В результаті вони отримали назву чисел Черча. Функція на основі натуральних чисел називалася λ-обчислюваною. Було і інше визначення. Функція з тези Черча називається λ-обчислюваною за двох умов. Перше звучало так: якщо вона була розрахована на елементах Черча, а другою умовою була можливість подання членом λ-числення.
Також в 1936 році, перш ніж вивчати роботу свого колеги, Тюрінг створив теоретичну модель для абстрактних машин, тепер званих його ім’ям. Вони могли б виконувати обчислення шляхом маніпулювання символами на стрічці. Це також відноситься до іншим математичним діям, знайденим в теоретичної інформатики, таких як квантові імовірнісні обчислення. Функція з тези Черча тільки згодом була обґрунтована з застосуванням машини Тюрінга. Спочатку вони спиралися на λ-числення.
