Часть лямбда-исчисления, имеющая отношение к вычислениям, теперь называется нетипизированным лямбда-исчислением.
Лямбда-исчисление можно использовать для определения вычислимой функции. Ни один общий алгоритм не может ответить на вопрос, эквивалентны ли два выражения лямбда-исчисления.