| |
VOLUME 2, ISSUE 4, PAPER 5
|
Solution of a Problem of Barendregt on Sensible λ-Theories
|
©Benedetto Intrigila, University of Rome 2, Italy
©Richard Statman, Carnegie-Mellon University \ Pittsburgh, PA,
|
Abstract
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.
|
Publication date: October 18, 2006
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-2(4:5)2006
Hit Counts: 2406 |
 Creative Commons | |
