{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T07:33:31Z","timestamp":1772609611474,"version":"3.50.1"},"reference-count":6,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":27860,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1937,12]]},"abstract":"<jats:p>Several definitions have been given to express an exact meaning corresponding to the intuitive idea of \u2018effective calculability\u2019 as applied for instance to functions of positive integers. The purpose of the present paper is to show that the computable functions introduced by the author are identical with the \u03bb-definable functions of Church and the general recursive functions due to Herbrand and G\u00f6del and developed by Kleene. It is shown that every \u03bb-definable function is computable and that every computable function is general recursive. There is a modified form of \u03bb-definability, known as \u03bb-<jats:italic>K<\/jats:italic>-definability, and it turns out to be natural to put the proof that every \u03bb-definable function is computable in the form of a proof that every \u03bb-<jats:italic>K<\/jats:italic>-definable function is computable; that every \u03bb-definable function is \u03bb-<jats:italic>K<\/jats:italic>-definable is trivial. If these results are taken in conjunction with an already available proof that every general recursive function is \u03bb-definable we shall have the required equivalence of computability with \u03bb-definability and incidentally a new proof of the equivalence of \u03bb-definability and \u03bb-<jats:italic>K<\/jats:italic>-definability.<\/jats:p><jats:p>A definition of what is meant by a computable function cannot be given satisfactorily in a short space. I therefore refer the reader to <jats:italic>Computable<\/jats:italic> pp. 230\u2013235 and p. 254. The proof that computability implies recursiveness requires no more knowledge of computable functions than the ideas underlying the definition: the technical details are recalled in \u00a75.<\/jats:p>","DOI":"10.2307\/2268280","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T14:29:03Z","timestamp":1146925743000},"page":"153-163","source":"Crossref","is-referenced-by-count":192,"title":["Computability and \u03bb-definability"],"prefix":"10.1017","volume":"2","author":[{"given":"A. M.","family":"Turing","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S002248120004072X_ref004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01565439"},{"key":"S002248120004072X_ref005","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-36-00227-2"},{"key":"S002248120004072X_ref001","first-page":"230","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"42","author":"Turing","year":"1936","journal-title":"Proceedings of the London Mathematical Society"},{"key":"S002248120004072X_ref003","doi-asserted-by":"publisher","DOI":"10.2307\/2371045"},{"key":"S002248120004072X_ref002","first-page":"103","volume":"1","author":"Post","year":"1936","journal-title":"Finite combinatory processes\u2014formulation 1"},{"key":"S002248120004072X_ref006","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1936-1501858-0"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248120004072X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T16:03:06Z","timestamp":1560009786000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002248120004072X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1937,12]]},"references-count":6,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1937,12]]}},"alternative-id":["S002248120004072X"],"URL":"https:\/\/doi.org\/10.2307\/2268280","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1937,12]]}}}