{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T22:51:09Z","timestamp":1675205469391},"reference-count":3,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":11972,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1981,6]]},"abstract":"<jats:p>In a recent article in this Journal (see [3]), J.P. Jones states and proves a theorem which purports to give an \u201cabsolute epistemological upper bound on the complexity of mathematical proofs\u201d for recursively axiomatizable theories. However, Jones' statement of this result is misleading, and in fact defective, as can be seen by a close analysis of it. Such an analysis is the object of the present note.<\/jats:p><jats:p>The main point is that Jones' \u201cepistemological bound\u201d can in no way be considered a computational bound on the complexity of proofs. Not only is the \u201cproof-theoretic interpretation of the number 243\u201d contained in Jones' article objectionable but, more fundamentally, there is in a strong sense no way one can hope to recover anything like the full force suggested by Jones' original statement of the theorem.<\/jats:p><jats:p>We wish to insist that our comments concern only the difficulties surrounding Jones' Corollary 1 on p. 338 of his article and not his ingenious construction of universal Diophantine representations of r.e. sets presented in the same article.<\/jats:p>","DOI":"10.2307\/2273619","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:55:50Z","timestamp":1146938150000},"page":"255-258","source":"Crossref","is-referenced-by-count":3,"title":["Complexity bounds on proofs"],"prefix":"10.1017","volume":"46","author":[{"given":"William S.","family":"Hatcher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernard R.","family":"Hodgson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200045722_ref002","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1976.11994142"},{"key":"S0022481200045722_ref001","first-page":"323","volume-title":"Mathematical developments arising from Hilbert problems. Proceedings of Symposia in Pure Mathematics","volume":"28","author":"Davis","year":"1976"},{"key":"S0022481200045722_ref003","first-page":"335","volume":"43","author":"Jones","year":"1978","journal-title":"Three universal representations of recursively enumerable sets"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200045722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T16:08:58Z","timestamp":1558800538000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200045722\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,6]]},"references-count":3,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1981,6]]}},"alternative-id":["S0022481200045722"],"URL":"https:\/\/doi.org\/10.2307\/2273619","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,6]]}}}