{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T22:19:27Z","timestamp":1784240367810,"version":"3.55.0"},"reference-count":17,"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":15351,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1972,3]]},"abstract":"<jats:p>The complexity of a computable function can be measured by considering the time or space required to compute its values. Particular notions of time and space arising from variants of Turing machines have been investigated by R. W. Ritchie [14], Hartmanis and Stearns [8], and Arbib and Blum [1], among others. General properties of such complexity measures have been characterized axiomatically by Rabin [12], Blum [2], Young [16], [17], and McCreight and Meyer [10].<\/jats:p><jats:p>In this paper the speed-up and super-speed-up theorems of Blum [2] are generalized to speed-up by arbitrary total effective operators. The significance of such theorems is that one cannot equate the complexity of a computable function with the running time of its fastest program, for the simple reason that there are computable functions which in a very strong sense have no fastest programs.<\/jats:p><jats:p>Let <jats:italic>\u03c6<jats:sub>i<\/jats:sub><\/jats:italic> be the <jats:italic>i<\/jats:italic>th partial recursive function of one variable in a standard G\u00f6del numbering of partial recursive functions. A family \u03a6<jats:sub>0<\/jats:sub>, \u03a6<jats:sub>1<\/jats:sub>, \u2026 of functions of one variable is called a <jats:italic>Blum measure on computation<\/jats:italic> providing<\/jats:p><jats:p>(1) domain (<jats:italic>\u03c6<jats:sub>i<\/jats:sub><\/jats:italic>) = domain (\u03a6<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>), and<\/jats:p><jats:p>(2) the predicate [\u03a6<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>(<jats:italic>x<\/jats:italic>) = <jats:italic>m<\/jats:italic>] is recursive in <jats:italic>i<\/jats:italic>, <jats:italic>x<\/jats:italic> and <jats:italic>m<\/jats:italic>.<\/jats:p><jats:p>Typical interpretations of \u03a6<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>(<jats:italic>x<\/jats:italic>) are the number of steps required by the <jats:italic>i<\/jats:italic>th Turing machine (in a standard enumeration of Turing machines) to converge on input <jats:italic>x<\/jats:italic>, the space or number of tape squares required by the <jats:italic>i<\/jats:italic>th Turing machine to converge on input <jats:italic>x<\/jats:italic> (with the convention that \u03a6<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>(<jats:italic>x<\/jats:italic>) is undefined even if the machine fails to halt in a finite loop), and the length of the shortest derivation of the value of \u03c6<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>(<jats:italic>x<\/jats:italic>) from the <jats:italic>i<\/jats:italic>th set of recursive equations.<\/jats:p>","DOI":"10.2307\/2272545","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:14:18Z","timestamp":1146935658000},"page":"55-68","source":"Crossref","is-referenced-by-count":39,"title":["Computational speed-up by effective operators"],"prefix":"10.1017","volume":"37","author":[{"given":"Albert R.","family":"Meyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrick C.","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200080543_ref012","volume-title":"Degree of difficulty of computing a function and a partial ordering of recursive sets","author":"Rabin","year":"1960"},{"key":"S0022481200080543_ref016","doi-asserted-by":"publisher","DOI":"10.1145\/321510.321525"},{"key":"S0022481200080543_ref004","doi-asserted-by":"publisher","DOI":"10.1145\/321637.321648"},{"key":"S0022481200080543_ref001","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0181538-0"},{"key":"S0022481200080543_ref002","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S0022481200080543_ref005","first-page":"24","volume-title":"Proceedings of the 1964 International Congress on Logic, Methodology and Philosophy of Science","author":"Cobham","year":"1964"},{"key":"S0022481200080543_ref006","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1969.27"},{"key":"S0022481200080543_ref011","first-page":"351","volume-title":"Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory","author":"Meyer"},{"key":"S0022481200080543_ref007","volume-title":"Computability and unsolvability","author":"Davis","year":"1958"},{"key":"S0022481200080543_ref008","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"S0022481200080543_ref010","first-page":"79","volume-title":"Conference Record of the ACM Symposium on Theory of Computing","author":"McCreight","year":"1969"},{"key":"S0022481200080543_ref014","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1963-0158822-2"},{"key":"S0022481200080543_ref015","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200080543_ref017","volume-title":"A note on \u201caxioms\u201d for computational complexity and computation of finite unctions","author":"Young","year":"1969"},{"key":"S0022481200080543_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90546-3"},{"key":"S0022481200080543_ref009","first-page":"21","volume":"36","author":"Helm","year":"1971","journal-title":"On size vs. efficiency for programs admitting speed-up"},{"key":"S0022481200080543_ref013","unstructured":"Ritchie D. M. , Program structure and computational complexity, Thesis, Division of Engineering and Applied Physics, Harvard University, 1968."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200080543","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T15:19:02Z","timestamp":1559315942000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200080543\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1972,3]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1972,3]]}},"alternative-id":["S0022481200080543"],"URL":"https:\/\/doi.org\/10.2307\/2272545","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1972,3]]}}}