A direct method for simulating partial recursive functions by Diophantine equations

Annals of Pure and Applied Logic 67 (1-3):325-348 (1994)
  Copy   BIBTEX

Abstract

A new proof is given of the celebrated theorem of M. Davis, H. Putnam and J. Robinson concerning exponential Diophantine representation of recursively enumerable predicates. The proof goes by induction on the defining scheme of a partial recursive function

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(94)90014-0

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

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

Ω in number theory.Toby Ord - 2007 - In C. S. Calude (ed.), Randomness and Complexity, from Leibniz to Chaitin. World Scientific. pp. 161-173.
Minimal realizability of intuitionistic arithmetic and elementary analysis.Zlatan Damnjanovic - 1995 - Journal of Symbolic Logic 60 (4):1208-1241.
Existential arithmetization of Diophantine equations.Yuri Matiyasevich - 2009 - Annals of Pure and Applied Logic 157 (2-3):225-233.
Some strongly undecidable natural arithmetical problems, with an application to intuitionistic theories.Panu Raatikainen - 2003 - Journal of Symbolic Logic 68 (1):262-266.
Review: Charles N. Delzell, Note on Quantifier Prefixes Over Diophantine Equations; J. P. Jones, H. Levitz, A. J. Wilkie, Classification of Quantifier Prefixes over Exponential Diophantine Equations. [REVIEW]Shih Ping Tung - 1988 - Journal of Symbolic Logic 53 (1):309-310.
Review: Louise Hay, On Creative Sets and Indices of Partial Recursive Functions; Louise Hay, Isomorphism Types of Index Sets of Partial Recursive Functions; Louise Hay, Index Sets of Finite Classes of Recursively Enumerable Sets. [REVIEW]Forbes D. Lewis - 1974 - Journal of Symbolic Logic 39 (1):186-187.
An invariance notion in recursion theory.Robert E. Byerly - 1982 - Journal of Symbolic Logic 47 (1):48-66.
The hereditary partial effective functionals and recursion theory in higher types.G. Longo & E. Moggi - 1984 - Journal of Symbolic Logic 49 (4):1319-1332.
The addition of bounded quantification and partial functions to a computational logic and its theorem prover.Robert Boyer - manuscript
Partial recursive functions and ω-functions.C. H. Applebaum & J. C. E. Dekker - 1970 - Journal of Symbolic Logic 35 (4):559-568.
An application of functional equations to the analysis of the invariance identities of classical gauge field theory.David Stapleton - 1991 - Foundations of Physics 21 (8):905-929.
Review: A. Nerode, A Decision Method for p-Adic Integral Zeros of Diophantine Equations. [REVIEW]Julia Robinson - 1965 - Journal of Symbolic Logic 30 (3):391-391.
Electrodynamics in terms of functions over the groupSU(2). I. The equation of the vector potential.A. O. Barut & S. Malin - 1975 - Foundations of Physics 5 (3):375-386.
Accessible recursive functions.Stanley S. Wainer - 1999 - Bulletin of Symbolic Logic 5 (3):367-388.

Analytics

Added to PP
2014-01-16

Downloads
20 (#720,454)

6 months
7 (#339,156)

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

Diophantine Induction.Richard Kaye - 1990 - Annals of Pure and Applied Logic 46 (1):1-40.
Computability of Recursive Functions.J. C. Shepherdson & H. E. Sturgis - 1967 - Journal of Symbolic Logic 32 (1):122-123.
Arithmetical problems and recursively enumerable predicates.Martin Davis - 1953 - Journal of Symbolic Logic 18 (1):33-41.

View all 12 references / Add more references