{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:27:39Z","timestamp":1773228459753,"version":"3.50.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2007,7,24]],"date-time":"2007-07-24T00:00:00Z","timestamp":1185235200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,12]]},"DOI":"10.1007\/s00224-007-9020-y","type":"journal-article","created":{"date-parts":[[2007,7,23]],"date-time":"2007-07-23T18:37:44Z","timestamp":1185215864000},"page":"464-470","source":"Crossref","is-referenced-by-count":3,"title":["A Hierarchy below the Halting Problem for Additive Machines"],"prefix":"10.1007","volume":"43","author":[{"given":"Christine","family":"Ga\u00dfner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,7,24]]},"reference":[{"key":"9020_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Am. Math. Soc. 21, 1\u201346 (1989)","journal-title":"Bull. Am. Math. Soc."},{"key":"9020_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (1998)"},{"key":"9020_CR3","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1006\/jcom.1995.1018","volume":"11","author":"F. Cucker","year":"1995","unstructured":"Cucker, F., Koiran, P.: Computing over the reals with addition and order: higher complexity classes. J. Complex. 11, 358\u2013376 (1995)","journal-title":"J. Complex."},{"key":"9020_CR4","doi-asserted-by":"crossref","unstructured":"Fournier, H., Koiran, P.: Lower bounds are not easier over the reals. In: ICALP\u20192000. Lecture Notes in Comput. Sci., vol.\u00a01853, pp.\u00a0832\u2013843 (2000)","DOI":"10.1007\/3-540-45022-X_70"},{"key":"9020_CR5","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0304-3975(93)00063-B","volume":"133","author":"P. Koiran","year":"1994","unstructured":"Koiran, P.: Computing over the reals with addition and order. Theor. Comput. Sci. 133, 35\u201347 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9020_CR6","doi-asserted-by":"crossref","unstructured":"Meer, K., Ziegler, M.: An explicit solution to Post\u2019s problem over the reals. In: 15th International Symposium on Fundamentals of Computation Theory. Lecture Notes in Comput. Sci., vol. 3623, pp.\u00a0456\u2013467 (2005)","DOI":"10.1007\/11537311_41"},{"key":"9020_CR7","unstructured":"Meer, K., Ziegler, M.: On the word problem for a class of groups with infinite presentations. Preprint (2006)"},{"key":"9020_CR8","doi-asserted-by":"crossref","unstructured":"Meer, K., Ziegler, M.: Uncomputability below the real Halting Problem. In: CiE2006. Lecture Notes in Comput. Sci., vol. 3988, pp. 368\u2013377 (2006)","DOI":"10.1007\/11780342_39"},{"key":"9020_CR9","unstructured":"Meer, K., Ziegler, M.: An explicit solution to Post\u2019s problem over the reals. J. Complex. 23 (2007, to appear). Available online 20 April 2007"},{"key":"9020_CR10","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E.L. Post","year":"1944","unstructured":"Post, E.L.: Recursively enumerable sets of positive integers and their decision problems. Bull. Am. Math. Soc. 50, 284\u2013316 (1944)","journal-title":"Bull. Am. Math. Soc."},{"key":"9020_CR11","doi-asserted-by":"crossref","unstructured":"Tucker, J.V., Zucker, J.I.: Computable functions and semicomputable sets on many-sorted algebras. In: Abramskz, S., Gabbay, D., Maibaum, T. (eds.) Handbook of Logic in Computer Science, vol. 5, pp. 317\u2013523. Oxford University Press (2000)","DOI":"10.1093\/oso\/9780198537816.003.0008"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9020-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9020-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9020-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T08:18:09Z","timestamp":1629447489000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9020-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,24]]},"references-count":11,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["9020"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9020-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,24]]}}}