{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T17:45:19Z","timestamp":1778607919302,"version":"3.51.4"},"reference-count":109,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":6345,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[1996,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the informal concept of \u201ccomputability\u201d or \u201ceffective calculability\u201d and two of the formalisms commonly used to define it, \u201c(<jats:italic>Turing<\/jats:italic>)<jats:italic>computability<\/jats:italic>\u201d and \u201c(<jats:italic>general<\/jats:italic>)<jats:italic>recursiveness<\/jats:italic>\u201d. We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas.<\/jats:p><jats:p>After a careful historical and conceptual analysis of computability and recursion we make several recommendations in section \u00a77 about preserving the<jats:italic>intensional<\/jats:italic>differences between the concepts of \u201ccomputability\u201d and \u201crecursion.\u201d Specifically we recommend that: the term \u201crecursive\u201d should no longer carry the additional meaning of \u201ccomputable\u201d or \u201cdecidable;\u201d functions defined using Turing machines, register machines, or their variants should be called \u201ccomputable\u201d rather than \u201crecursive;\u201d we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be \u201c<jats:italic>Computability Theory<\/jats:italic>\u201d or simply<jats:italic>Computability<\/jats:italic>rather than \u201cRecursive Function Theory.\u201d<\/jats:p>","DOI":"10.2307\/420992","type":"journal-article","created":{"date-parts":[[2006,5,7]],"date-time":"2006-05-07T07:09:17Z","timestamp":1146985757000},"page":"284-321","source":"Crossref","is-referenced-by-count":120,"title":["Computability and Recursion"],"prefix":"10.1017","volume":"2","author":[{"given":"Robert I.","family":"Soare","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600007836_ref096","volume-title":"Proceedings of the 10th international congress of logic, methodology, and philosophy ofscience, August 19\u201325, 1995, Florence, Italy","author":"Tamburrini","year":"1995"},{"key":"S1079898600007836_ref104","first-page":"7","article-title":"Solvable and unsolvable problems","volume":"31","author":"Turing","year":"1954","journal-title":"Science News"},{"key":"S1079898600007836_ref101","first-page":"139","article-title":"Text of a lecture by Turing on June 24, 1949","volume":"6","author":"Turing","year":"1949","journal-title":"Annals of the History of Computing"},{"key":"S1079898600007836_ref093","volume-title":"Proceedings of the 10th international congress of logic, methodology, and philosophy of science, August 19\u201325, 1995, Florence, Italy","author":"Soare"},{"key":"S1079898600007836_ref087","volume-title":"Lecture notes in logic","author":"Shoenfield","year":"1991"},{"key":"S1079898600007836_ref092","volume-title":"Handbook of computability theory","author":"Soare"},{"key":"S1079898600007836_ref100","first-page":"3","article-title":"Intelligent machinery","volume":"5","author":"Turing","year":"1948","journal-title":"Machine Intelligence"},{"key":"S1079898600007836_ref099","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-45.1.161"},{"key":"S1079898600007836_ref097","first-page":"230","article-title":"On computable numbers, with an application to the Entscheidungsproblem, parts 3 and 4","volume":"42","author":"Turing","year":"1936","journal-title":"Proceedings of the London Mathematical Society"},{"key":"S1079898600007836_ref091","first-page":"302","volume-title":"Skrifter utgit av Videnskapsselskapet i Kristiania, I. Mathematisk-Naturvidenskabelig Klasse","volume":"6","author":"Skolem","year":"1923"},{"key":"S1079898600007836_ref102","doi-asserted-by":"publisher","DOI":"10.1093\/mind\/LIX.236.433"},{"key":"S1079898600007836_ref088","doi-asserted-by":"crossref","unstructured":"[Shoenfield, 1995] Shoenfield J. R. , The mathematical work of S. C. Kleene, this Bulletin, vol. 1, pp. 8\u201343.","DOI":"10.2307\/420945"},{"key":"S1079898600007836_ref095","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1079898600007836_ref106","volume-title":"From Frege to Godel, a sourcebook in mathematical logic, 1879\u20131931","author":"Heijenoort","year":"1967"},{"key":"S1079898600007836_ref103","doi-asserted-by":"publisher","DOI":"10.2307\/1969481"},{"key":"S1079898600007836_ref108","doi-asserted-by":"publisher","DOI":"10.2307\/2974762"},{"key":"S1079898600007836_ref098","doi-asserted-by":"publisher","DOI":"10.2307\/2268280"},{"key":"S1079898600007836_ref080","doi-asserted-by":"publisher","DOI":"10.2307\/2371809"},{"key":"S1079898600007836_ref071","first-page":"83","volume-title":"Arithmetices principia, nova methodo exposita","author":"Peano","year":"1889"},{"key":"S1079898600007836_ref067","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"},{"key":"S1079898600007836_ref057","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-12.1.245"},{"key":"S1079898600007836_ref030","unstructured":"[G\u00f6del, 1972] G\u00f6del K. , Some remarks on the undecidability results, in G\u00f6del 1990, pp. 305\u2013306, written in 1972."},{"key":"S1079898600007836_ref026","unstructured":"[G\u00f6del, 1946] G\u00f6del K. , Remarks before the Princeton bicentennial conference of problems in mathematics, reprinted in Davis 1965, pp. 84\u201388."},{"key":"S1079898600007836_ref085","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12013-2"},{"key":"S1079898600007836_ref034","doi-asserted-by":"crossref","unstructured":"[Harrington and Soare, 1996] Harrington L. and Soare R. I. , Definability, automorphisms, and dynamic properties of computably enumerable sets, this Bulletin, vol. 2, 1996, pp. 199\u2013213.","DOI":"10.2307\/421110"},{"key":"S1079898600007836_ref009","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139171496","volume-title":"Computability: An introduction to recursive function theory","author":"Cutiand","year":"1980"},{"key":"S1079898600007836_ref001","volume-title":"Computability and logic","author":"Boolos","year":"1974"},{"key":"S1079898600007836_ref027","unstructured":"[G\u00f6del, 1951] G\u00f6del K. , Some basic theorems on the foundations of mathematics and their implications, in G\u00f6del 1995, pp. 304\u2013323. (This was the Gibbs Lecture delivered by Godel on December 26, 1951 to the American Mathematical Society)."},{"key":"S1079898600007836_ref073","volume-title":"Volume II: Elements of logic","author":"Peirce","year":"1960"},{"key":"S1079898600007836_ref055","first-page":"1","article-title":"Recursive functionals and quantifiers of finite type I","volume":"91","author":"Kleene","year":"1959","journal-title":"Transactions of the American Mathematical Society"},{"key":"S1079898600007836_ref068","volume-title":"Lecture notes in mathematics","author":"Normann","year":"1980"},{"key":"S1079898600007836_ref013","doi-asserted-by":"crossref","unstructured":"[Davis, 1988] Davis M. , Mathematical logic and the origin of modern computers, in Herken, 1988, pp. 149\u2013174.","DOI":"10.1093\/oso\/9780198537748.003.0005"},{"key":"S1079898600007836_ref017","doi-asserted-by":"crossref","unstructured":"[Feferman, 1988] Feferman S. , Turing in the land of O(z), in Herken, 1988, pp. 113\u2013147.","DOI":"10.1093\/oso\/9780198537748.003.0004"},{"key":"S1079898600007836_ref024","unstructured":"[G\u00f6del, 1934] G\u00f6del K. , On undecidable propositions of formal mathematical systems, notes by S. C. Kleene and J. B. Rosser on lectures at the Institute for Advanced Study, Princeton, New Jersey, 1934, reprinted in Davis 1965, pp. 39\u201374]."},{"key":"S1079898600007836_ref060","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1981-14920-X"},{"key":"S1079898600007836_ref036","volume-title":"Grundlagen der Geometrie","author":"Hilbert","year":"1899"},{"key":"S1079898600007836_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1938-06720-1"},{"key":"S1079898600007836_ref070","volume-title":"Oxford english dictionary","author":"Simpson","year":"1989"},{"key":"S1079898600007836_ref063","first-page":"49","volume-title":"G\u00f6del remembered","author":"Kleene","year":"1987"},{"key":"S1079898600007836_ref064","doi-asserted-by":"crossref","unstructured":"[Kleene, 1988] Kleene S. C. , Turing's analysis of computability, and major applications of it, in Herken 1988, pp. 17\u201354.","DOI":"10.1093\/oso\/9780198537748.003.0002"},{"key":"S1079898600007836_ref016","volume-title":"Computability: computable functions, logic, and the foundations of mathematics","author":"Epstein","year":"1989"},{"key":"S1079898600007836_ref004","doi-asserted-by":"publisher","DOI":"10.2307\/2269326"},{"key":"S1079898600007836_ref081","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"S1079898600007836_ref079","unstructured":"[Post, 1941] Post E. L. , Absolutely unsolvable problems and relatively undecidable propositions: Account of an anticipation, submitted for publication in 1941; printed in Davis 1965, pp. 340\u2013433."},{"key":"S1079898600007836_ref015","volume-title":"Was sind und was sollen die Zahlen?","author":"Dedekind","year":"1888"},{"key":"S1079898600007836_ref053","doi-asserted-by":"publisher","DOI":"10.2307\/2372632"},{"key":"S1079898600007836_ref005","doi-asserted-by":"crossref","first-page":"42","DOI":"10.2307\/2268808","article-title":"Review of Turing 1936","volume":"2","author":"Church","year":"1937","journal-title":"Journal of Symbolic Logic"},{"key":"S1079898600007836_ref043","volume-title":"Alan Turing: The enigma","author":"Hodges","year":"1983"},{"key":"S1079898600007836_ref051","first-page":"679","volume-title":"Proceedings of the international congress of mathematicians, Cambridge, Massachusetts, U.S.A., August 30-September 6, 1950","volume":"1","author":"Kleene","year":"1952"},{"key":"S1079898600007836_ref077","unstructured":"[Platek, 1966] Platek R. , Foundations of recursion theory, Ph.D. thesis , Stanford University, Stanford, CA."},{"key":"S1079898600007836_ref083","first-page":"641","article-title":"Degrees of recursive unsolvability: preliminary report (abstract)","volume":"54","author":"Post","year":"1948","journal-title":"Bulletin of the American Mathematical Society"},{"key":"#cr-split#-S1079898600007836_ref025.1","unstructured":"[G\u00f6del, 1936] G\u00f6del K. , On the length of proofs, G\u00f6del 1986, pp. 397-399"},{"key":"#cr-split#-S1079898600007836_ref025.2","unstructured":"reprinted in Davis 1965, pp. 82-83, with a Remark added in proof [of the original German publication]."},{"key":"S1079898600007836_ref047","doi-asserted-by":"publisher","DOI":"10.2307\/2267778"},{"key":"S1079898600007836_ref040","first-page":"65","article-title":"Abhandlungen aus dem mathematischen Seminar derHamburgischen Universit\u00e4t","volume":"6","author":"Hilbert","year":"1928","journal-title":"Die Grundlagen der Mathematik"},{"key":"S1079898600007836_ref038","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457115"},{"key":"S1079898600007836_ref042","volume-title":"Grundlagen der Mathematik I (1934), II (1939)","volume":"I","author":"Hilbert","year":"1934"},{"key":"S1079898600007836_ref049","doi-asserted-by":"publisher","DOI":"10.2307\/2371894"},{"key":"S1079898600007836_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71257-6"},{"key":"S1079898600007836_ref022","unstructured":"[G\u00f6del, 193?] G\u00f6del K. , Undecidable diophantine propositions, in G\u00f6del 1995, pp. 156\u2013175."},{"key":"S1079898600007836_ref010","volume-title":"Computability and unsolvability","author":"Davis","year":"1958"},{"key":"S1079898600007836_ref021","doi-asserted-by":"crossref","unstructured":"[Gandy, 1988] Gandy R. , The confluence of ideas in 1936, in Herken, 1988, pp. 55\u2013111.","DOI":"10.1093\/oso\/9780198537748.003.0003"},{"key":"S1079898600007836_ref050","volume-title":"Introduction to metamathematics","author":"Kleene","year":"1952"},{"key":"S1079898600007836_ref075","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448046"},{"key":"S1079898600007836_ref006","doi-asserted-by":"crossref","first-page":"43","DOI":"10.2307\/2268812","article-title":"Review of Post 1936","volume":"2","author":"Church","year":"1937","journal-title":"Journal of Symbolic Logic"},{"key":"S1079898600007836_ref002","first-page":"332","article-title":"An unsolvable problem of elementary number theory","volume":"41","author":"Church","year":"1935","journal-title":"Bulletin of the American Mathematical Society"},{"key":"S1079898600007836_ref033","volume-title":"Collected works volume III: Unpublished essays and lectures","author":"G\u00f6del","year":"1995"},{"key":"S1079898600007836_ref052","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1955-0070594-4"},{"key":"S1079898600007836_ref031","volume-title":"Collected works volume I: Publications 1929\u201336","author":"G\u00f6del","year":"1986"},{"key":"S1079898600007836_ref090","unstructured":"[Sieg and Byrnes, 1995] Sieg W. and Byrnes J. , K-graph machines: generalizing Turing's machines and arguments, preprint."},{"key":"S1079898600007836_ref058","first-page":"106","article-title":"Recursive functionals and quantifiers offinite type II","volume":"108","author":"Kleene","year":"1963","journal-title":"Transactions of the American Mathematical Society"},{"key":"S1079898600007836_ref039","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206605"},{"key":"S1079898600007836_ref072","first-page":"256","article-title":"Sul concetto di num\u00e9ro","volume":"1","author":"Peano","year":"1891","journal-title":"Rivista di Matematica"},{"key":"S1079898600007836_ref044","doi-asserted-by":"publisher","DOI":"10.1007\/BF01565439"},{"key":"S1079898600007836_ref045","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-36-00227-2"},{"key":"S1079898600007836_ref032","volume-title":"Collected works volume II: Publications 1938\u20131974","author":"G\u00f6del","year":"1990"},{"key":"S1079898600007836_ref105","first-page":"106","volume-title":"A. M. Turing's ACE report of 1946 and other papers","author":"Turing","year":"1986"},{"key":"S1079898600007836_ref065","first-page":"379","article-title":"The upper semi-lattice of degrees of recursive unsolvability","volume":"59","author":"Kleene","year":"1954","journal-title":"Annals ofMathematics"},{"key":"S1079898600007836_ref078","doi-asserted-by":"publisher","DOI":"10.2307\/2269031"},{"key":"S1079898600007836_ref048","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1943-0007371-8"},{"key":"S1079898600007836_ref023","doi-asserted-by":"publisher","DOI":"10.1007\/BF01700692"},{"key":"S1079898600007836_ref066","volume-title":"Mathematical thought from ancient to modern times","author":"Kline","year":"1972"},{"key":"S1079898600007836_ref059","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1981.10004"},{"key":"S1079898600007836_ref074","volume-title":"Shadows of the mind","author":"Penrose","year":"1994"},{"key":"S1079898600007836_ref082","doi-asserted-by":"publisher","DOI":"10.2307\/2267170"},{"key":"S1079898600007836_ref014","volume-title":"Stetigkeit und irrational Zahlen","author":"Dedekind","year":"1872"},{"key":"S1079898600007836_ref076","volume-title":"Rekursive funktionen","author":"P\u00e9ter","year":"1951"},{"key":"S1079898600007836_ref028","doi-asserted-by":"publisher","DOI":"10.1111\/j.1746-8361.1958.tb01464.x"},{"key":"S1079898600007836_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)91226-8"},{"key":"S1079898600007836_ref003","doi-asserted-by":"publisher","DOI":"10.2307\/2371045"},{"key":"S1079898600007836_ref084","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1995-00606-3"},{"key":"S1079898600007836_ref037","first-page":"174","volume-title":"Verhandlungen des Dritten Internationalen Mathematiker-Kongresses in Heidelberg vom 8. bis 13. August 1904","author":"Hilbert","year":"1905"},{"key":"S1079898600007836_ref061","volume-title":"Proc. sympos. algorithms in modern mathematics and computer science (dedicated to Al-Khowarizimi), Urgench, Khorezm Region, Uzbek, SSSR, 1979","author":"Kleene","year":"1981"},{"key":"S1079898600007836_ref008","doi-asserted-by":"crossref","first-page":"11","DOI":"10.4064\/fm-28-1-11-21","article-title":"Formal definitions in the theory ofordinal numbers","volume":"28","author":"Church","year":"1936","journal-title":"Fundamenta Mathematicae"},{"key":"S1079898600007836_ref029","unstructured":"[G\u00f6del, 1964] G\u00f6del K. , Postscriptum to G\u00f6del 1931, written in 1946, printed in Davis 1965, pp. 71\u201373."},{"key":"S1079898600007836_ref054","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1955-09896-3"},{"key":"S1079898600007836_ref041","volume-title":"Grundz\u00fcge der theoretischen Logik","author":"Hilbert","year":"1928"},{"key":"S1079898600007836_ref046","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1936-06353-6"},{"key":"S1079898600007836_ref011","volume-title":"The undecidable. Basicpaperson undecidablepropositions, unsolvable problems, andcomputable functions","author":"Davis","year":"1965"},{"key":"S1079898600007836_ref086","volume-title":"Mathematical logic","author":"Shoenfield","year":"1967"},{"key":"S1079898600007836_ref056","first-page":"38","volume-title":"Logic, methodology, and philosophy of science: Proceedings of the 1960 international congress","author":"Kleene","year":"1962"},{"key":"S1079898600007836_ref018","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1515\/9783110870299.314","volume-title":"The space of mathematics","author":"Feferman","year":"1992"},{"key":"S1079898600007836_ref089","volume-title":"Mathematics and mind","author":"Sieg","year":"1994"},{"key":"S1079898600007836_ref019","volume-title":"Computability theory, semantics, and logicprogramming","author":"Fitting","year":"1987"},{"key":"S1079898600007836_ref035","volume-title":"The universal Turing machine: A half-century survey","author":"Herken","year":"1988"},{"key":"S1079898600007836_ref062","first-page":"490","volume-title":"Notre Dame Journal of Formal Logic","volume":"28","author":"Kleene","year":"1987"},{"key":"S1079898600007836_ref094","volume-title":"Recursion theory and computational complexity","author":"Soare","year":"1981"},{"key":"S1079898600007836_ref107","volume-title":"Webster's third new international dictionary of the English language (unabridged)","author":"Gove","year":"1993"},{"key":"S1079898600007836_ref069","volume-title":"Classical recursion theory","author":"Od\u0153reddi","year":"1989"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600007836","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,4]],"date-time":"2024-02-04T07:36:52Z","timestamp":1707032212000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600007836\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":109,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["S1079898600007836"],"URL":"https:\/\/doi.org\/10.2307\/420992","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}