Recursion in Partial Type‐1 Objects With Well‐Behaved Oracles

Mathematical Logic Quarterly 42 (1):449-460 (1996)
  Copy   BIBTEX

Abstract

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

Categories

Keywords

Reprint years

DOI

10.1002/malq.19960420137

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 106,169

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Prenex normal form theorems in semi-classical arithmetic.Makoto Fujiwara & Taishi Kurahashi - 2021 - Journal of Symbolic Logic 86 (3):1124-1153.
Extremal numberings and fixed point theorems.Marat Faizrahmanov - 2022 - Mathematical Logic Quarterly 68 (4):398-408.
Other Proofs of Old Results.Henryk Kotlarski - 1998 - Mathematical Logic Quarterly 44 (4):474-480.
Effective Nonrecursiveness.Takeshi Yamaguchi - 1997 - Mathematical Logic Quarterly 43 (1):45-48.
Selected logic papers.Gerald E. Sacks - 1999 - River Edge, N.J.: World Scientific.
Oracles and Query Lower Bounds in Generalised Probabilistic Theories.Howard Barnum, Ciarán M. Lee & John H. Selby - 2018 - Foundations of Physics 48 (8):954-981.
The weakness of the Erdős–Moser theorem under arithmetic reductions.Ludovic Levy Patey & Ahmed Mimouni - forthcoming - Journal of Mathematical Logic.
On A Theorem Equivalent to Post's Fundamental Theorem of Recursive Function Theory.Albert A. Mullin - 1963 - Mathematical Logic Quarterly 9 (12‐15):203-205.
A double arity hierarchy theorem for transitive closure logic.Martin Grohe & Lauri Hella - 1996 - Archive for Mathematical Logic 35 (3):157-171.
A uniformly computable Implicit Function Theorem.Timothy H. McNicholl - 2008 - Mathematical Logic Quarterly 54 (3):272-279.

Analytics

Added to PP
2013-12-01

Downloads
22 (#1,071,209)

6 months
1 (#1,597,699)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Recursion-theoretic hierarchies.Peter G. Hinman - 1978 - New York: Springer Verlag.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

View all 6 references / Add more references