Я знаю, что невозможно определить эквивалентность для нетипизированного лямбда-исчисления. Цитирование Барендрегта, Л. П. Лямбда-исчисление: его синтаксис и семантика. Северная Голландия, Амстердам (1984). :ββ\beta Если A и B являются непересекающимися непустыми множествами лямбда-членов, замкнутых...
Слабая нормализация для простого типизированного лямбда-исчисления может быть доказана (Тьюринг) индукцией по . Расширенное лямбда-исчисление с рекурсорами на натуральные числа (Генцен) имеет слабую стратегию нормализации по индукции на ϵ 0 .ω2ω2\omega^2ϵ0ϵ0\epsilon_0 А как насчет системы F (или...
Я знаю, что исчисление конструкций сильно нормализуется, то есть у каждого выражения есть норма, которая не может быть бета, далее сокращена. Так что на самом деле это наиболее эффективное выражение, которое вычисляет то же значение, что и исходное выражение. Но в некоторых случаях нормализация...