Теорема Чёрча – Россера

В лямбда-исчислении теорема Чёрча -Россера утверждает, что при применении правил приведения к членам порядок, в котором выбираются сокращения, не влияет на конечный результат.

Точнее, если существуют две различные редукции или последовательности редукций, которые можно применить к одному и тому же термину, то существует термин, достижимый из обоих результатов путем применения (возможно, пустых) последовательностей дополнительных редукций. ^[1] Теорема была доказана в 1936 году Алонсо Чёрчем и Дж. Баркли Россером , в честь которых она названа.

Теорема символизируется расположенной рядом диаграммой: если термин a можно свести к b и c , то должен существовать дополнительный член d (возможно, равный либо b , либо c ), к которому можно свести и b , и c . Рассматривая лямбда-исчисление как абстрактную систему переписывания , теорема Чёрча-Россера утверждает, что правила редукции лямбда-исчисления конфлюэнтны . Как следствие теоремы, термин в лямбда-исчислении имеет не более одной нормальной формы , что оправдывает ссылку на « нормальную форму» данного нормализуемого термина.

История

В 1936 году Алонсо Чёрч и Дж. Баркли Россер доказали, что эта теорема справедлива для β-редукции в λI-исчислении (в котором каждая абстрактная переменная должна присутствовать в теле термина). Метод доказательства известен как «конечность разработок», и он имеет дополнительные последствия, такие как теорема стандартизации, которая относится к методу, в котором сокращения могут выполняться слева направо для достижения нормальной формы (если таковая существует). Результат для чистого нетипизированного лямбда-исчисления был доказан Д. Э. Шрёером в 1965 году. ^[2]

Чистое нетипизированное лямбда-исчисление

Одним из типов редукции в чистом нетипизированном лямбда-исчислении, к которому применяется теорема Черча-Россера, является β-редукция, при которой подчлен формы сжимается путем замены . Если β-редукция обозначается через , а ее рефлексивное транзитивное замыкание через, то теорема Чёрча – Россера такова: ^[3] ${\displaystyle (\lambda x.t)s}$ ${\displaystyle t[x:=s]}$ ${\displaystyle \rightarrow _{\beta }}$ ${\displaystyle \twoheadrightarrow _{\beta }}$

${\displaystyle \forall M,N_{1},N_{2}\in \Lambda :{\text{if}}\ M\twoheadrightarrow _{\beta }N_{1}\ {\text{and}}\ M\twoheadrightarrow _{\beta }N_{2}\ {\text{then}}\ \exists X\in \Lambda :N_{1}\twoheadrightarrow _{\beta }X\ {\text{and}}\ N_{2}\twoheadrightarrow _{\beta }X}$

Следствием этого свойства является то, что два термина, равные по , должны сводиться к одному общему члену: ^[4] ${\displaystyle \lambda \beta }$

${\displaystyle \forall M,N\in \Lambda :{\text{if}}\ \lambda \beta \vdash M=N\ {\text{then}}\ \exists X:M\twoheadrightarrow _{\beta }X\ {\text{and}}\ N\twoheadrightarrow _{\beta }X}$

Теорема также применима к η-редукции, в которой подтерм заменяется на . Это также применимо к βη-редукции, объединению двух правил редукции. ${\displaystyle \lambda x.Sx}$ ${\displaystyle S}$

Доказательство

Один из методов доказательства β-редукции принадлежит Уильяму Тейту и Перу Мартину-Лёфу . ^[5] Скажем, что бинарное отношение удовлетворяет свойству ромба, если: ${\displaystyle \rightarrow }$

${\displaystyle \forall M,N_{1},N_{2}\in \Lambda :{\text{if}}\ M\rightarrow N_{1}\ {\text{and}}\ M\rightarrow N_{2}\ {\text{then}}\ \exists X\in \Lambda :N_{1}\rightarrow X\ {\text{and}}\ N_{2}\rightarrow X}$

Тогда свойство Чёрча-Россера является утверждением, удовлетворяющим свойству алмаза. Мы вводим новую редукцию, рефлексивное транзитивное замыкание которой является свойством ромба. Таким образом, индукцией по числу ступеней приведения следует, что удовлетворяет свойству ромба. ${\displaystyle \twoheadrightarrow _{\beta }}$ ${\displaystyle \rightarrow _{\|}}$ ${\displaystyle \twoheadrightarrow _{\beta }}$ ${\displaystyle \twoheadrightarrow _{\beta }}$

Отношение имеет правила формирования: ${\displaystyle \rightarrow _{\|}}$

• ${\displaystyle M\rightarrow _{\|}M}$
• Если и тогда и и ${\displaystyle M\rightarrow _{\|}M'}$ ${\displaystyle N\rightarrow _{\|}N'}$ ${\displaystyle \lambda x.M\rightarrow _{\|}\lambda x.M'}$ ${\displaystyle MN\rightarrow _{\|}M'N'}$ ${\displaystyle (\lambda x.M)N\rightarrow _{\|}M'[x:=N']}$

Можно напрямую доказать, что правило η-редукции является правилом Чёрча – Россера. Тогда можно доказать, что β-редукция и η-редукция коммутируют в том смысле, что: ^[6]

Если и тогда существует такой термин, что и . ${\displaystyle M\rightarrow _{\beta }N_{1}}$ ${\displaystyle M\rightarrow _{\eta }N_{2}}$ ${\displaystyle X}$ ${\displaystyle N_{1}\rightarrow _{\eta }X}$ ${\displaystyle N_{2}\rightarrow _{\beta }X}$

Отсюда можно заключить, что βη-редукция является редукцией Чёрча–Россера. ^[7]

Нормализация

Правило редукции, удовлетворяющее свойству Чёрча-Россера, обладает тем свойством, что каждый терм M может иметь не более одной отличной нормальной формы, а именно: если X и Y являются нормальными формами M , то по свойству Чёрча-Россера они оба сводятся к равный член Z . Оба термина уже являются нормальными формами, так что . ^[4] ${\displaystyle X=Z=Y}$

Если редукция является сильно нормализующей (нет бесконечных путей редукции), то из слабой формы свойства Чёрча – Россера следует полное свойство (см. лемму Ньюмана ). Слабым свойством для отношения является: ^[8] ${\displaystyle \rightarrow }$

${\displaystyle \forall M,N_{1},N_{2}\in \Lambda :}$если и тогда существует такой термин, что и . ${\displaystyle M\rightarrow N_{1}}$ ${\displaystyle M\rightarrow N_{2}}$ ${\displaystyle X}$ ${\displaystyle N_{1}\twoheadrightarrow X}$ ${\displaystyle N_{2}\twoheadrightarrow X}$

Варианты

Теорема Чёрча-Россера также справедлива для многих вариантов лямбда-исчисления, таких как просто типизированное лямбда-исчисление , многие исчисления с расширенными системами типов и исчисление бета-значений Гордона Плоткина . Плоткин также использовал теорему Чёрча-Россера, чтобы доказать, что оценка функциональных программ (как для ленивой оценки , так и для нетерпеливой оценки ) является функцией от программ к значениям ( подмножество лямбда-членов).

В более старых исследовательских работах говорится, что система переписывания является системой Чёрча-Россера или обладает свойством Чёрча-Россера, если она является конфлюэнтной .

Примечания

1. Алама (2017).
2. Барендрегт (1984), с. 283.
3. Барендрегт (1984), с. 53–54.
4. Барендрегт (1984), с. 54.
5. Барендрегт (1984), с. 59-62.
6. Барендрегт (1984), с. 64–65.
7. Барендрегт (1984), с. 66.
8. Барендрегт (1984), с. 58.

Рекомендации

• Алама, Джесси (2017). Залта, Эдвард Н. (ред.). Стэнфордская энциклопедия философии (изд. осени 2017 г.). Лаборатория метафизических исследований Стэнфордского университета.
• Церковь, Алонсо ; Россер, Дж. Баркли (май 1936 г.), «Некоторые свойства преобразования» (PDF) , Transactions of the American Mathematical Society , 39 (3): 472–482, doi : 10.2307/1989762 , JSTOR  1989762.
• Барендрегт, Хендрик Питер (1984), Лямбда-исчисление: его синтаксис и семантика, Исследования по логике и основам математики, том. 103 (пересмотренная редакция), Северная Голландия, Амстердам, ISBN 0-444-87508-5, заархивировано из оригинала 23 августа 2004 г.. Ошибка.