Classes of Numeration Models of λ-Calculus

✍ Scribed by Akira Kanda

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 439 KB
• Volume: 32
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19860321904

✦ Synopsis

Th.-2-calculus developed by CHVRCH [ 2 ] is the following formal system: Let F' be a countable set of variables.

Dcfiiiition 1.1. (2-terms).

1. If .c E V . then x is a A-term.

2 .

If -11 and L are 2-terms, then (ML) is a A-term.

We denote the set of all 2-terms by T .

We assume a natural meaning of a R-term occurring in some other /%term. An occurrrnc(3 of a variable x in M is bound if it is inside a part of i V of the form (Ax:.M). Otherwiisr it is free. For any terms M , L and a variable %, the result of substituting L for each frer occurrence of x in M (and changing bound variables to avoid clashes) is denoted by M [ x : = L].

The calculus has the following three reduction rules :

K. e cl n c t i o n R u 1 e s. (a) (?.bc.X) -+ (3.y.,W[z : = y]) if x is not bound in i W and y does not occur in M . (/9) ((l..L..JI) L ) --f M [ x : = L].