Search

• < Previous
• 1
• Next >

---

The Omega Rule is $\mathbf{\Pi_{1}^{1}}$-Complete in the $\lambda\beta$-Calculus

Benedetto Intrigila ; Richard Statman.

In a functional calculus, the so called \Omega-rule states that if two terms P and Q applied to any closed term <i>N</i> return the same value (i.e. PN = QN), then they are equal (i.e. P = Q holds). As it is well known, in the \lambda\beta-calculus the \Omega-rule does not hold, even when the&nbsp;[&hellip;]

---

Addressing Machines as models of lambda-calculus

Giuseppe Della Penna ; Benedetto Intrigila ; Giulio Manzonetto.

Turing machines and register machines have been used for decades in theoretical computer science as abstract models of computation. Also the $\lambda$-calculus has played a central role in this domain as it allows to focus on the notion of functional computation, based on the substitution mechanism,&nbsp;[&hellip;]

---