Benedetto Intrigila ; Richard Statman - Solution of a Problem of Barendregt on Sensible lambda-Theories

lmcs:2241 - Logical Methods in Computer Science, October 18, 2006, Volume 2, Issue 4 - https://doi.org/10.2168/LMCS-2(4:5)2006
Solution of a Problem of Barendregt on Sensible lambda-TheoriesArticle

Authors: Benedetto Intrigila ; Richard Statman

H is the theory extending β-conversion by identifying all closed unsolvables. Hω is the closure of this theory under the ω-rule (and β-conversion). A long-standing conjecture of H. Barendregt states that the provable equations of Hω form Π11-complete set. Here we prove that conjecture.

Comment: 17 pages

https://doi.org/10.2168/LMCS-2(4:5)2006
Source: arXiv.org:cs/0609080
Volume: Volume 2, Issue 4
Published on: October 18, 2006
Imported on: December 9, 2005
Keywords: Computer Science - Logic in Computer Science, F.4.1
Licence: arXiv.org - Assumed non-exclusive license to distribute

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 2984 times.
This article's PDF has been downloaded 411 times.