Uncomputability below the real halting problem

Cited 8 time in webofscience Cited 8 time in scopus
  • Hit : 305
  • Download : 0
Most of the existing work in real number computation theory concentrates on complexity issues rather than computability aspects. Though some natural problems like deciding membership in the Mandelbrot set or in the set of rational numbers are known to be undecidable in the Blum-Shub-Smale (BSS) model of computation over the reals, there has not been much work on different degrees of undecidability. A typical question into this direction is the real version of Post's classical problem: Are there some explicit undecidable problems below the real Halting Problem? In this paper we study three different topics related to such questions: First an extension of a positive answer to Post's problem to the linear setting. We then analyze how additional real constants increase the power of a BSS machine. And finally a real variant of the classical word problem for groups is presented which we establish reducible to and from (that is, complete for) the BSS Halting problem.
Publisher
SPRINGER-VERLAG BERLIN
Issue Date
2006
Language
English
Article Type
Article; Proceedings Paper
Keywords

MACHINES; COMPUTATION; COMPLEXITY; FIELDS; ORDER

Citation

LOGICAL APPROACHES TO COMPTATIONAL BARRIERS, PROCEEDINGS, v.3988, pp.368 - 377

ISSN
0302-9743
DOI
10.1007/11780342_39
URI
http://hdl.handle.net/10203/203401
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 8 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0