{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T21:42:16Z","timestamp":1648935736906},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":14621,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1974,3]]},"abstract":"Let be the set of recursive functions computable by machines using at most t(x)<\/jats:italic> computation steps on argument x<\/jats:italic>, for all but finitely many inputs x<\/jats:italic>. We call t<\/jats:italic> a name for the complexity class . Suppose we allow our machines to run longer, say h(x, t(x))<\/jats:italic> steps on argument x<\/jats:italic>, where h<\/jats:italic> is some fixed recursive function. One might expect that, for large enough h<\/jats:italic>, permitting our machines to run longer by an amount h<\/jats:italic> will always allow us to compute new functions, i.e., is a proper subset of . This turns out not to be the case: The \u201cgap theorem\u201d ([2], [3]) implies that for every recursive h<\/jats:italic> there exists a recursive t<\/jats:italic> such that . However, if we restrict our attention to names from a certain subclass of the recursive functions, then we can indeed uniformly increase the size of our -classes. Informally, we call a recursive function t<\/jats:italic> \u201chonest\u201d if some machine computes t(x)<\/jats:italic> in roughly t(x)<\/jats:italic> steps for each argument x<\/jats:italic>. (A precise definition is given in Definition 1 below.) Then according to the \u201ccompression theorem\u201d [1], there exists a single recursive function h<\/jats:italic> such that, for every honest t<\/jats:italic>, is a proper subset of . Thus the phenomenon of the gap theorem is avoided by restricting attention to honest functions. It is a surprising consequence of the \u201chonesty theorem\u201d of McCreight and Meyer ([4], [5]) that there is no loss of generality in this restriction. Namely, for any recursive function t<\/jats:italic> there is an honest recursive function t<\/jats:italic>\u2032 such that .<\/jats:p>","DOI":"10.2307\/2272353","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:27:55Z","timestamp":1146950875000},"page":"127-138","source":"Crossref","is-referenced-by-count":4,"title":["Honest bounds for complexity classes of recursive functions"],"prefix":"10.1017","volume":"39","author":[{"given":"R.","family":"Moll","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. R.","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S002248120006552X_ref016","unstructured":"Young P. , Easy constructions in complexity theory: speed-up and gap theorems, Technical Report No. 57, Department of Computer Science, Purdue University, Lafayette, Ind., 1971."},{"key":"S002248120006552X_ref015","first-page":"61","volume-title":"Proceedings of the Third Annual Switching and Automata Theory Symposium","author":"Meyer","year":"1972"},{"key":"S002248120006552X_ref014","doi-asserted-by":"publisher","DOI":"10.1145\/321679.321692"},{"key":"S002248120006552X_ref012","doi-asserted-by":"publisher","DOI":"10.1145\/321650.321661"},{"key":"S002248120006552X_ref010","first-page":"258","volume-title":"Proceedings of the Third Annual Symposium on the Theory of Computing","author":"Robertson","year":"1971"},{"key":"S002248120006552X_ref006","doi-asserted-by":"crossref","unstructured":"Bass L. , Hierarchies based on computational complexity and irregularities of class determining measured sets, Doctoral Thesis, Purdue University, Lafayette, Ind., 1970.","DOI":"10.1145\/800161.805147"},{"key":"S002248120006552X_ref004","doi-asserted-by":"crossref","unstructured":"McCreight E. M. and Meyer A. R. , Classes of computable functions defined by bounds on computation: Preliminary report, Association for Computing Machinery Symposium on the Theory of Computing, 1969, pp. 79\u201388.","DOI":"10.1145\/800169.805423"},{"key":"S002248120006552X_ref002","doi-asserted-by":"publisher","DOI":"10.1145\/321679.321691"},{"key":"S002248120006552X_ref001","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S002248120006552X_ref013","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321702"},{"key":"S002248120006552X_ref009","volume-title":"The theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S002248120006552X_ref011","volume-title":"Upward and downward diagonalizations over axiomatic complexity classes","author":"Constable","year":"1969"},{"key":"S002248120006552X_ref003","volume-title":"Complexity of algorithms and computations","author":"Trachtenbrot","year":"1967"},{"key":"S002248120006552X_ref005","doi-asserted-by":"crossref","unstructured":"McCreight E. M. , Classes of computable functions defined by bounds on computation, Doctoral Thesis, Computer Science Department, Carnegie-Mellon University, Pittsburgh, Pa, 1969.","DOI":"10.1145\/800169.805423"},{"key":"S002248120006552X_ref007","unstructured":"Bass L. and Young P. , Ordinal hierarchies and naming classes, Journal of the Association for Computing Machinery (to appear)."},{"key":"S002248120006552X_ref008","first-page":"154","volume-title":"Proceedings of the Third Annual Princeton Conference on Information Science and Systems, 1969","author":"Meyer"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248120006552X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T21:37:35Z","timestamp":1559165855000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002248120006552X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,3]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1974,3]]}},"alternative-id":["S002248120006552X"],"URL":"https:\/\/doi.org\/10.2307\/2272353","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1974,3]]}}}