{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T11:25:31Z","timestamp":1751887531205},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":11880,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1981,9]]},"abstract":"<jats:p>In this paper we show how some of the finite injury priority arguments can be simplified by making explicit use of the primitive notions of axiomatic computational complexity theory. Phrases such as \u201cperform <jats:italic>n<\/jats:italic> steps in the enumeration of <jats:italic>W<jats:sub>i<\/jats:sub><\/jats:italic>\u201d certainly bear witness to the fact that many of these complexity notions have been used implicitly from the early days of recursive function theory. However, other complexity notions such as that of an \u201chonest\u201d function are not so apparent, neither explicitly nor implicitly. Accordingly, one of the main factors in our simplification of these diagonalization arguments is the replacement of the characteristic function <jats:italic>\u03c7<jats:sub>A<\/jats:sub><\/jats:italic> of a set <jats:italic>A<\/jats:italic> by the function <jats:italic>\u03bd<jats:sub>A<\/jats:sub><\/jats:italic>, which is the next-element function of the set <jats:italic>A<\/jats:italic>. Another important factor is the use of busy beaver sets (see [3]) to provide the basis for the required diagonalizations thereby permitting rather simple and explicit descriptions of the sets constructed. Although the differences between the priority method and our method of construction are subtle, they are nonetheless real and noteworthy.<\/jats:p><jats:p>In preparation for the results which follow we devote the remainder of this section to the requisite definitions and notions as well as some preliminary lemmas. A more comprehensive discussion of many of the notions in this section can be found in [3]. Since we will be dealing extensively with relative computations most of our notions here have been correspondingly relativized.<\/jats:p>","DOI":"10.2307\/2273749","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:56:46Z","timestamp":1146952606000},"page":"460-474","source":"Crossref","is-referenced-by-count":3,"title":["Busy beaver sets and the degrees of unsolvability"],"prefix":"10.1017","volume":"46","author":[{"given":"Robert P.","family":"Daley","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200045333_ref003","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19780241303"},{"key":"S0022481200045333_ref009","volume-title":"Theory of recursive functions and effective computahility","author":"Rogers","year":"1967"},{"key":"S0022481200045333_ref004","volume-title":"Busy beaver sets and the degrees of unsolvability","author":"Daley","year":"1977"},{"key":"S0022481200045333_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/BF02219729"},{"key":"S0022481200045333_ref010","first-page":"513","volume":"41","author":"Soare","year":"1976","journal-title":"The infinite injury priority method"},{"key":"S0022481200045333_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90546-3"},{"key":"S0022481200045333_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1976-0403933-6"},{"key":"S0022481200045333_ref001","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S0022481200045333_ref008","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"S0022481200045333_ref006","unstructured":"van Emde Boas P. , Abstract resource-bound classes, Ph.D. Dissertation, Matematisch Centrum, Amsterdam, 1974."},{"key":"S0022481200045333_ref011","volume-title":"Degrees of unsolvability","author":"Shoenfield","year":"1971"},{"key":"S0022481200045333_ref012","unstructured":"Symes M. , The extension of machine-independent computational complexity theory to oracle machine computation and to the computation of finite functions, Ph.D. Dissertation, Department of Applied Analysis and Computer Science, University of Waterloo, 1971."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200045333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T19:43:49Z","timestamp":1558813429000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200045333\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,9]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1981,9]]}},"alternative-id":["S0022481200045333"],"URL":"https:\/\/doi.org\/10.2307\/2273749","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,9]]}}}