Теорема Черча–Россера
-
Теорема Черча-Россера
- Утверждает, что каждое нормальное выражение в лямбда-исчислении может быть сведено к нормальной форме.
- Используется для доказательства свойств лямбда-исчисления и других систем рекурсии.
-
Доказательство теоремы
- Доказательство основано на свойствах бинарного отношения редукции.
- Используется свойство алмаза для доказательства свойства Черча-Россера.
- Вводится новое сокращение, удовлетворяющее свойству алмаза и используемое для доказательства.
-
Нормализация и варианты
- Нормализация позволяет каждому члену иметь только одну нормальную форму.
- Теорема применима к различным вариантам лямбда-исчисления.
-
Рекомендации и ошибки
- Статья содержит рекомендации по форматированию и ошибки в HTML-коде.