{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:08:35Z","timestamp":1759147715559},"reference-count":2,"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>In the theory of conversion it is important to have a formally defined function which assigns to any positive integer <jats:italic>n<\/jats:italic> the least integer not less than <jats:italic>n<\/jats:italic> which has a given property. The definition of such a formula is somewhat involved: I propose to give the corresponding formula in \u03bb-<jats:italic>K<\/jats:italic>-conversion, which will (naturally) be much simpler. I shall in fact find a formula \u00fe such that if <jats:italic>T<\/jats:italic> be a formula for which <jats:italic>T<\/jats:italic>(<jats:italic>n<\/jats:italic>) is convertible to a formula representing a natural number, whenever <jats:italic>n<\/jats:italic> represents a natural number, then \u00fe(<jats:italic>T, r<\/jats:italic>) is convertible to the formula <jats:italic>q<\/jats:italic> representing the least natural number <jats:italic>q<\/jats:italic>, not less than <jats:italic>r<\/jats:italic>, for which <jats:italic>T<\/jats:italic>(<jats:italic>q<\/jats:italic>) conv 0.<jats:sup>2<\/jats:sup> The method depends on finding a formula \u0398 with the property that \u0398 conv \u03bb<jats:italic>u<\/jats:italic>\u00b7<jats:italic>u<\/jats:italic>(\u0398(<jats:italic>u<\/jats:italic>)), and consequently if <jats:italic>M<\/jats:italic>\u2192\u0398(<jats:italic>V<\/jats:italic>) then <jats:italic>M<\/jats:italic> conv <jats:italic>V<\/jats:italic>(<jats:italic>M<\/jats:italic>). A formula with this property is,<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200040731_eqnU01\" \/><\/jats:disp-formula><\/jats:p><jats:p>The formula \u00fe will have the required property if \u00fe(<jats:italic>T, r<\/jats:italic>) conv <jats:italic>r<\/jats:italic> when <jats:italic>T<\/jats:italic>(<jats:italic>r<\/jats:italic>) conv 0, and \u00fe(<jats:italic>T, r<\/jats:italic>) conv \u00fe(<jats:italic>T, S<\/jats:italic>(<jats:italic>r<\/jats:italic>)) otherwise. These conditions will be satisfied if \u00fe(<jats:italic>T, r<\/jats:italic>) conv <jats:italic>T<\/jats:italic>(<jats:italic>r<\/jats:italic>, \u03bb<jats:italic>x<\/jats:italic>\u00b7\u00fe(<jats:italic>T<\/jats:italic>, <jats:italic>S<\/jats:italic>(<jats:italic>r<\/jats:italic>)), <jats:italic>r<\/jats:italic>), i.e. if \u00fe conv {\u03bb<jats:italic>ptr<\/jats:italic>\u00b7<jats:italic>t<\/jats:italic>(<jats:italic>r<\/jats:italic>, \u03bb<jats:italic>x<\/jats:italic>\u00b7<jats:italic>p<\/jats:italic>(<jats:italic>t<\/jats:italic>, <jats:italic>S<\/jats:italic>(<jats:italic>r<\/jats:italic>)), <jats:italic>r<\/jats:italic>)}(\u00fe). We therefore put,<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200040731_eqnU02\" \/><\/jats:disp-formula><\/jats:p><jats:p>This enables us to define also a formula,<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200040731_eqnU03\" \/><\/jats:disp-formula><\/jats:p><jats:p>such that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200040731_inline01\" \/>(<jats:italic>T, n<\/jats:italic>) is convertible to the formula representing the <jats:italic>n<\/jats:italic>th positive integer <jats:italic>q<\/jats:italic> for which <jats:italic>T<\/jats:italic>(<jats:italic>q<\/jats:italic>) conv 0.<\/jats:p>","DOI":"10.2307\/2268281","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:29:03Z","timestamp":1146940143000},"page":"164-164","source":"Crossref","is-referenced-by-count":20,"title":["The \u00fe-function in \u03bb-<i>K<\/i>-conversion"],"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":"S0022481200040731_ref001","first-page":"231","article-title":"A theory of positive integers in formal logic","volume":"57","author":"Kleene","year":"1934","journal-title":"American journal of mathematics"},{"key":"S0022481200040731_ref002","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-36-00227-2"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200040731","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T20:03:15Z","timestamp":1560024195000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200040731\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1937,12]]},"references-count":2,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1937,12]]}},"alternative-id":["S0022481200040731"],"URL":"https:\/\/doi.org\/10.2307\/2268281","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1937,12]]}}}