We give a many-one reduction of the set of true \Pi^1_1 sentences to the set of consequences of the lambda-calculus with the omega-rule. This solves in the affirmative a long-standing problem of H. Barendregt (1975). © Springer-Verlag Berlin Heidelberg 2007.
Intrigila, B., Statman, R. (2007). The omega rule is \Pi^1_1-complete in the lambda-calculus. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.178-193).
The omega rule is \Pi^1_1-complete in the lambda-calculus
INTRIGILA, BENEDETTO;
2007-01-01
Abstract
We give a many-one reduction of the set of true \Pi^1_1 sentences to the set of consequences of the lambda-calculus with the omega-rule. This solves in the affirmative a long-standing problem of H. Barendregt (1975). © Springer-Verlag Berlin Heidelberg 2007.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
