Church–Rosser theorem

Church–Rosser theorem In lambda calculus, the Church–Rosser theorem states that, when applying reduction rules to terms, the ordering in which the reductions are chosen does not make a difference to the eventual result.

Più precisamente, if there are two distinct reductions or sequences of reductions that can be applied to the same term, then there exists a term that is reachable from both results, by applying (possibly empty) sequences of additional reductions.[1] The theorem was proved in 1936 by Alonzo Church and J. Barkley Rosser, da cui prende il nome.

The theorem is symbolized by the adjacent diagram: If term a can be reduced to both b and c, then there must be a further term d (possibly equal to either b or c) to which both b and c can be reduced. Viewing the lambda calculus as an abstract rewriting system, the Church–Rosser theorem states that the reduction rules of the lambda calculus are confluent. As a consequence of the theorem, a term in the lambda calculus has at most one normal form, justifying reference to "the normal form" of a given normalizable term.

Contenuti 1 Storia 2 Pure untyped lambda calculus 2.1 Prova 3 Normalisation 4 Variants 5 Appunti 6 Riferimenti Storia In 1936, Alonzo Church and J. Barkley Rosser proved that the theorem holds for β-reduction in the λI-calculus (in which every abstracted variable must appear in the term's body). The proof method is known as "finiteness of developments", and it has additional consequences such as the Standardization Theorem, which relates to a method in which reductions can be performed from left to right to reach a normal form (se ne esiste uno). The result for the pure untyped lambda calculus was proved by D. e. Shroer in 1965.[2] Pure untyped lambda calculus One type of reduction in the pure untyped lambda calculus for which the Church–Rosser theorem applies is β-reduction, in which a subterm of the form {stile di visualizzazione (lambda x.t)S} is contracted by the substitution {stile di visualizzazione t[X:=s]} . If β-reduction is denoted by {displaystyle rightarrow _{beta }} and its reflexive, transitive closure by {displaystyle twoheadrightarrow _{beta }} then the Church–Rosser theorem is that:[3] {displaystyle forall M,N_{1},N_{2}in Lambda :{testo{Se}} Mtwoheadrightarrow _{beta }N_{1} {testo{e}} Mtwoheadrightarrow _{beta }N_{2} {testo{poi}} exists Xin Lambda :N_{1}twoheadrightarrow _{beta }X {testo{e}} N_{2}twoheadrightarrow _{beta }X} A consequence of this property is that two terms equal in {displaystyle lambda beta } must reduce to a common term:[4] {displaystyle forall M,Nin Lambda :{testo{Se}} lambda beta vdash M=N {testo{poi}} exists X:Mtwoheadrightarrow _{beta }X {testo{e}} Ntwoheadrightarrow _{beta }X} The theorem also applies to η-reduction, in which a subterm {displaystyle lambda x.Sx} is replaced by {stile di visualizzazione S} . It also applies to βη-reduction, the union of the two reduction rules.

Proof For β-reduction, one proof method originates from William W. Tait and Per Martin-Löf.[5] Say that a binary relation {displaystyle rightarrow } satisfies the diamond property if: {displaystyle forall M,N_{1},N_{2}in Lambda :{testo{Se}} Mrightarrow N_{1} {testo{e}} Mrightarrow N_{2} {testo{poi}} exists Xin Lambda :N_{1}rightarrow X {testo{e}} N_{2}rightarrow X} Then the Church–Rosser property is the statement that {displaystyle twoheadrightarrow _{beta }} satisfies the diamond property. We introduce a new reduction {displaystyle rightarrow _{|}} whose reflexive transitive closure is {displaystyle twoheadrightarrow _{beta }} and which satisfies the diamond property. By induction on the number of steps in the reduction, it thus follows that {displaystyle twoheadrightarrow _{beta }} satisfies the diamond property.

The relation {displaystyle rightarrow _{|}} has the formation rules: {displaystyle Mrightarrow _{|}M} Se {displaystyle Mrightarrow _{|}M'} e {displaystyle Nrightarrow _{|}N'} poi {displaystyle lambda x.Mrightarrow _{|}lambda x.M'} e {displaystyle MNrightarrow _{|}M'N'} e {stile di visualizzazione (lambda x.M)Nrightarrow _{|}M'[X:=N']} The η-reduction rule can be proved to be Church–Rosser directly. Quindi, it can be proved that β-reduction and η-reduction commute in the sense that:[6] Se {displaystyle Mrightarrow _{beta }N_{1}} e {displaystyle Mrightarrow _{eta }N_{2}} then there exists a term {stile di visualizzazione X} tale che {stile di visualizzazione N_{1}rightarrow _{eta }X} e {stile di visualizzazione N_{2}rightarrow _{beta }X} .

Hence we can conclude that βη-reduction is Church–Rosser.[7] Normalisation A reduction rule that satisfies the Church–Rosser property has the property that every term M can have at most one distinct normal form, come segue: if X and Y are normal forms of M then by the Church–Rosser property, they both reduce to an equal term Z. Both terms are already normal forms so {displaystyle X=Z=Y} .[4] If a reduction is strongly normalising (there are no infinite reduction paths) then a weak form of the Church–Rosser property implies the full property (see Newman's lemma). The weak property, for a relation {displaystyle rightarrow } , è:[8] {displaystyle forall M,N_{1},N_{2}in Lambda :} Se {displaystyle Mrightarrow N_{1}} e {displaystyle Mrightarrow N_{2}} then there exists a term {stile di visualizzazione X} tale che {stile di visualizzazione N_{1}twoheadrightarrow X} e {stile di visualizzazione N_{2}twoheadrightarrow X} . Variants The Church–Rosser theorem also holds for many variants of the lambda calculus, such as the simply-typed lambda calculus, many calculi with advanced type systems, and Gordon Plotkin's beta-value calculus. Plotkin also used a Church–Rosser theorem to prove that the evaluation of functional programs (for both lazy evaluation and eager evaluation) is a function from programs to values (a subset of the lambda terms).

In older research papers, a rewriting system is said to be Church–Rosser, or to have the Church–Rosser property, when it is confluent.

Notes ^ Alama (2017). ^ Barendregt (1984), p. 283. ^ Barendregt (1984), p. 53–54. ^ Salta su: a b Barendregt (1984), p. 54. ^ Barendregt (1984), p. 59-62. ^ Barendregt (1984), p. 64–65. ^ Barendregt (1984), p. 66. ^ Barendregt (1984), p. 58. References Alama, Jesse (2017). Zalta, Edoardo N. (ed.). La Stanford Encyclopedia of Philosophy (Autunno 2017 ed.). Laboratorio di ricerca sulla metafisica, Università di Stanford. Church, Alonzo; Rosser, J. Barkley (Maggio 1936), "Some properties of conversion" (PDF), Transazioni dell'American Mathematical Society, 39 (3): 472–482, doi:10.2307/1989762, JSTOR 1989762. Barendregt, Hendrik Pieter (1984), The Lambda Calculus: Its Syntax and Semantics, Studies in Logic and the Foundations of Mathematics, vol. 103 (Revised ed.), North Holland, Amsterdam, ISBN 0-444-87508-5, archiviato dall'originale in poi 2004-08-23. Errata. Categorie: Lambda calculusTheorems in the foundations of mathematicsRewriting systems

Se vuoi conoscere altri articoli simili a Church–Rosser theorem puoi visitare la categoria Lambda calculus.

lascia un commento

L'indirizzo email non verrà pubblicato.

Vai su

Utilizziamo cookie propri e di terze parti per migliorare l'esperienza dell'utente Maggiori informazioni