Related Publications (1)

Classification of Quantifier Prefixes Over Diophantine Equations

Academic

Publications

Two universal 3-quantifier representations of recursively enumerable sets

Two universal 3-quantifier representations of recursively enumerable sets,Yuri Matiyasevich,Julia Robinson

Edit

Two universal 3-quantifier representations of recursively enumerable sets (Citations: 5)


	BibTex \| RIS \| RefWorks Download

It is proved that all recursively enumerable sets of natural numbers can be represented by arithmetic formulas (of two kinds) with only 3 quantifiers.

Published in 2008.

Cumulative Annual

View Publication

( adsabs.harvard.edu )

( arxiv.org )

Citation Context (3)

- ...[MR74] The quantifier prefix ∃∃∀∃ is undecidable, i.e., there is no Turing machine which decides for an arbitrary input f ∈ Z[u,v,x,y] whether there is a (u,v) ∈N 2 such that ∀x ∃y with f(u,v,x,y)=0...
- ...Russian readers may be a better reference than the original reference [MR74]...
J. Maurice Rojas. Uncomputably large integral points on algebraic plane curves?
- ...For example, Matiyasevich and Julia Robinson have shown [MR74, Jon81] that sentences of the form ∃u ∃v ∀x ∃y f(u, v, x, y) ? =0 are already undecidable...
J. Maurice Rojas. On the complexity of diophantine geometry in low dimensions (extended ...
- ...For example, Matiyasevich and Julia Robinson have shown [MR74, Jon81] that sentences of the form ∃u ∃v ∀x ∃y f(u, v, x, y) ? =0 are already undecidable...
A. Rojas, et al. On the Complexity of Diophantine Geometry in Low Dimensions

References (4)

Some Representations of Diophantine Sets (Citations: 2)

Journal: Journal of Symbolic Logic - JSYML , vol. 37, no. 3, pp. 572-578, 1972

An Unsolvable Problem in Number Theory (Citations: 6)

Journal: Journal of Symbolic Logic - JSYML , vol. 25, no. 3, pp. 220-232, 1960

Arithmetical Problems and Recursively Enumerable Predicates (Citations: 13)

Journal: Journal of Symbolic Logic - JSYML , vol. 18, no. 1, pp. 33-41, 1953

Arithmetical Representation of Recursively Enumerable Sets (Citations: 5)

Journal: Journal of Symbolic Logic - JSYML , vol. 21, no. 2, pp. 162-186, 1956

Sort by:

Citations (5)

Computational Arithmetic Geometry I. Sentences Nearly in the Polynomial Hierarchy (Citations: 5)

Journal: Journal of Computer and System Sciences - JCSS , vol. 62, no. 2, pp. 216-235, 2001

Algebraic Geometry Over Four Rings and the Frontier to Tractability (Citations: 11)

Published in 2000.

Uncomputably large integral points on algebraic plane curves? (Citations: 3)

Journal: Theoretical Computer Science - TCS , vol. 235, no. 1, pp. 145-162, 2000

On the complexity of diophantine geometry in low dimensions (extended abstract)

Conference: ACM Symposium on Theory of Computing - STOC , pp. 527-536, 1999

On the Complexity of Diophantine Geometry in Low Dimensions (Citations: 1)

Published in 1998.