Premium
Recursion in Partial Type‐1 Objects With Well‐Behaved Oracles
Author(s) -
Tourlakis George
Publication year - 1996
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19960420137
Subject(s) - mathematics , recursion (computer science) , closure (psychology) , computability theory , computability , hierarchy , primitive recursive function , type (biology) , algebra over a field , mathematics subject classification , discrete mathematics , pure mathematics , algorithm , ecology , economics , market economy , biology
We refine the definition of II‐computability of [12] so that oracles have a “consistent”, but natural, behaviour. We prove a Kleene Normal Form Theorem and closure of semi‐recursive relations under ∃ 1 . We also show that in this more inclusive computation theory Post's theorem in the arithmetical hierarchy still holds. Mathematics Subject Classification: 03D65, 03D75.