{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T22:10:26Z","timestamp":1737065426114,"version":"3.33.0"},"reference-count":18,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3603,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1997,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We survey the research performed in the last few years on a specific topic: the power of real machines over binary inputs. This research attempts to characterize the classes of decision problems over a finite alphabet \u2010 say {0,1} \u2010 which can be decided by real machines working under several resource restrictions. Non\u2010uniformity appears here in a natural way. However, since this is a technical concept which is not widely known, we summarize in Section 2 some of the intuitive notions, as well as a few basic theorems related to it. In Section 3 we do this for the subject of real machines and then, in Section 4 we present the state of the art of the surveyed topic. We devote Section 1 to introduce the main concepts of complexity theory. Proofs in this article are quite sketchy and are included more to convey intuitive ideas than to completely prove the claimed statements. Bibliographical references to the original literature are supplied for the latter purpose.<\/jats:p>","DOI":"10.1002\/malq.19970430202","type":"journal-article","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T20:56:30Z","timestamp":1180817790000},"page":"143-157","source":"Crossref","is-referenced-by-count":1,"title":["Machines Over the Reals and Non\u2010Uniformity"],"prefix":"10.1002","volume":"43","author":[{"given":"Felipe","family":"Cucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"volume-title":"Complexity and Real Computation","author":"Blum L.","key":"e_1_2_1_2_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_2","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_2","DOI":"10.1137\/0206054"},{"key":"e_1_2_1_5_2","first-page":"83","volume-title":"Computer Algebra, Symbolic and Algebraic Computation","author":"Collins G.","year":"1982"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_2","DOI":"10.1016\/S0747-7171(88)80008-7"},{"author":"Cucker F.","journal-title":"SIAM J. Computing","article-title":"On the power of real Turing machines over binary inputs","key":"e_1_2_1_7_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_2","DOI":"10.1006\/jcom.1995.1018"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_2","DOI":"10.1007\/BF01387193"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_2","DOI":"10.1016\/0304-3975(94)00069-7"},{"key":"e_1_2_1_11_2","first-page":"191","article-title":"Turing machines that take advice","volume":"28","author":"Karp R.","year":"1982","journal-title":"L'Enseignement Math\u00e9matique"},{"doi-asserted-by":"crossref","unstructured":"Koiran P. A weak version of the Blum Shub and Smale model. In: 34thAnnual IEEE Symposium on Foundations of Computer Science1993 pp.486\u2013495.","key":"e_1_2_1_12_2","DOI":"10.1109\/SFCS.1993.366838"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_2","DOI":"10.1016\/0304-3975(93)00063-B"},{"doi-asserted-by":"crossref","unstructured":"Maass W. Bounds for the computational power and learning complexity of analog neural nets. In: 25thAnnual ACM Symposium on the Theory of Computing1993 pp.335\u2013344.","key":"e_1_2_1_14_2","DOI":"10.1145\/167088.167193"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_2","DOI":"10.1145\/322276.322287"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_2","DOI":"10.1137\/0204018"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_2","DOI":"10.1016\/0304-3975(94)90178-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_2","DOI":"10.1112\/plms\/s2-42.1.230"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_2","DOI":"10.2307\/1994937"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19970430202","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19970430202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:44:43Z","timestamp":1737063883000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19970430202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["10.1002\/malq.19970430202"],"URL":"https:\/\/doi.org\/10.1002\/malq.19970430202","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}