{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:26:20Z","timestamp":1775838380597,"version":"3.50.1"},"reference-count":34,"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":8593,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1990,9]]},"abstract":"<jats:p>A notion of reducibility \u2264<jats:sub><jats:italic>r<\/jats:italic><\/jats:sub> between sets is specified by giving a set of procedures for computing one set from another. We say that a set <jats:italic>A<\/jats:italic> is <jats:italic>r-reducible<\/jats:italic> to a set <jats:italic>B, A<\/jats:italic> \u2264<jats:sub><jats:italic>r<\/jats:italic><\/jats:sub><jats:italic>B<\/jats:italic>, if one of the procedures applied to <jats:italic>B<\/jats:italic> gives <jats:italic>A<\/jats:italic>. Associated with any such reducibility notion is the structure <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200025500_inline1\"\/> of <jats:italic>r<\/jats:italic>-degrees, the equivalence classes of sets with respect to this reducibility, with the induced ordering. The most general notion of a computable reducibility is that of Turing, \u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub>. Here we say that <jats:italic>A<\/jats:italic> \u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub><jats:italic>B<\/jats:italic> if there is a Turing machine \u03c6<jats:sub><jats:italic>e<\/jats:italic><\/jats:sub> which, when equipped with an oracle for <jats:italic>B<\/jats:italic>, computes <jats:italic>A<\/jats:italic>: <jats:italic>\u03c6<\/jats:italic><jats:sub arrange=\"stack\"><jats:italic>e<\/jats:italic><\/jats:sub><jats:sup arrange=\"stack\"><jats:italic>B<\/jats:italic><\/jats:sup> = <jats:italic>A<\/jats:italic>. Such Turing degree computations are characterized by the phenomenon that only during the computation itself do we discover which questions about <jats:italic>B<\/jats:italic> need to be answered to compute <jats:italic>A(x)<\/jats:italic>. In contrast, for nearly all other computable reducibilities the set of questions needed is given in advance by a recursive procedure. Perhaps the most common example of such a procedure is many-one reducibility, \u2264<jats:sub><jats:italic>m<\/jats:italic><\/jats:sub>: <jats:italic>A<\/jats:italic> \u2264<jats:sub><jats:italic>m<\/jats:italic><\/jats:sub><jats:italic>B<\/jats:italic> if there is a recursive function <jats:italic>f<\/jats:italic> such that <jats:italic>x<\/jats:italic> \u2208 <jats:italic>A<\/jats:italic> \u21d4 <jats:italic>f<\/jats:italic>(<jats:italic>x<\/jats:italic>) \u2208 <jats:italic>B<\/jats:italic>.<\/jats:p><jats:p>Reducibilities with the property that the output, <jats:italic>A<\/jats:italic>(<jats:italic>x<\/jats:italic>), is determined by the answers that <jats:italic>B<\/jats:italic> gives to a set of questions calculated recursively from <jats:italic>x<\/jats:italic> are said to be of tabular type. The most general tabular reducibility is called <jats:italic>truth-table<\/jats:italic> reducibility, \u2264<jats:sub>tt<\/jats:sub>. The procedures [<jats:italic>e<\/jats:italic>] associated with this reducibility are specified by a recursive function <jats:italic>f<\/jats:italic> (= {<jats:italic>e<\/jats:italic>}) which, for each <jats:italic>x<\/jats:italic>, gives a set of <jats:italic>n<\/jats:italic> questions about the oracle and, for each of the possible 2<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> sets of answers, gives the corresponding output. As usual this defines <jats:italic>A<\/jats:italic> \u2264<jats:sub>tt<\/jats:sub><jats:italic>B<\/jats:italic> as \u201cthere is an e such that [<jats:italic>e<\/jats:italic>]<jats:sup><jats:italic>B<\/jats:italic><\/jats:sup> = <jats:italic>A<\/jats:italic>\u201d. It is with this notion of reducibility and the associated tt-degrees that we shall be concerned in this paper. Basic information on several such strong reducibilities can be found in Rogers [28]. For more information we recommend the survey articles by Odifreddi [25] and Degtev [2] as well as Odifreddi's book [26].<\/jats:p>","DOI":"10.2307\/2274468","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:36:50Z","timestamp":1146955010000},"page":"987-1006","source":"Crossref","is-referenced-by-count":6,"title":["Undecidability and initial segments of the (r.e.) tt-degrees"],"prefix":"10.1017","volume":"55","author":[{"given":"Christine Ann","family":"Haught","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard A.","family":"Shore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200025500_ref009","unstructured":"[9] Harrington L. and Slaman T. , Interpreting arithmetic in the Turing degrees of the recursively enumerable sets (to appear)."},{"key":"S0022481200025500_ref008","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1982-14970-9"},{"key":"S0022481200025500_ref005","unstructured":"[5] Fejer P. and Shore R. , Minimal tt- and wtt-degrees, to appear in the proceedings of a conference in Oberwolfach, 03 1989."},{"key":"S0022481200025500_ref004","first-page":"37","article-title":"Elementary theories","volume":"20","author":"Ershov","year":"1965","journal-title":"Uspekhi Matematicheskikh Nauk"},{"key":"S0022481200025500_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF02485250"},{"key":"S0022481200025500_ref011","doi-asserted-by":"crossref","unstructured":"[11] Haught C. A. and Shore R. , Initial segments of the wtt-degrees below 0\u2032, to appear in the proceedings of a conference in Oberwolfach, 03 1989.","DOI":"10.1007\/BFb0086120"},{"key":"S0022481200025500_ref007","unstructured":"[7] Harrington L. and Haught C. A. , Limitations on initial segment embeddings in the r.e. tt-degrees (to appear)."},{"key":"S0022481200025500_ref002","first-page":"137","article-title":"On truth-table-like reducibilities in the theory of algorithms","volume":"34","author":"Degtev","year":"1979","journal-title":"Uspekhi Matematicheskikh Nauk"},{"key":"S0022481200025500_ref014","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19680143002"},{"key":"S0022481200025500_ref017","first-page":"326","article-title":"Recursively enumerable many-one degrees","volume":"11","author":"Lachlan","year":"1972","journal-title":"Algebra i Logika"},{"key":"S0022481200025500_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70940-6"},{"key":"S0022481200025500_ref016","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-010-6"},{"key":"S0022481200025500_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0076217"},{"key":"S0022481200025500_ref018","first-page":"5","article-title":"Effective inseparability of the sets of identically true formulas and finitely refutable formulas for certain elementary theories","volume":"2","author":"Lavrov","year":"1963","journal-title":"Algebra i Logika"},{"key":"S0022481200025500_ref010","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1987-0882702-4"},{"key":"S0022481200025500_ref012","doi-asserted-by":"publisher","DOI":"10.2307\/1969708"},{"key":"S0022481200025500_ref027","first-page":"56","volume-title":"Logic, methodology and philosophy of science. II","author":"Rabin","year":"1965"},{"key":"S0022481200025500_ref034","doi-asserted-by":"publisher","DOI":"10.2307\/1969604"},{"key":"S0022481200025500_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BF02219290"},{"key":"S0022481200025500_ref021","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1988-0973174-0"},{"key":"S0022481200025500_ref013","first-page":"507","article-title":"On tt-degrees of r.e. T-degrees","volume":"106","author":"Kozbev","year":"1978","journal-title":"Matematicheskii; Sbornik"},{"key":"S0022481200025500_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"},{"key":"S0022481200025500_ref020","doi-asserted-by":"publisher","DOI":"10.2307\/1970779"},{"key":"S0022481200025500_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669003"},{"key":"S0022481200025500_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71260-6"},{"key":"S0022481200025500_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(80)90004-2"},{"key":"S0022481200025500_ref025","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1981-14863-1"},{"key":"S0022481200025500_ref026","volume-title":"Classical recursion theory: the theory of functions and sets of natural numbers","author":"Odifreddi","year":"1989"},{"key":"S0022481200025500_ref028","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200025500_ref030","unstructured":"[30] Shore R. and Slaman T. , Working below a low2 recursively enumerable degree (to appear)."},{"key":"S0022481200025500_ref031","unstructured":"[31] Shore R. , Working below a high recursively enumerable degree (to appear)."},{"key":"S0022481200025500_ref032","doi-asserted-by":"publisher","DOI":"10.2307\/1971028"},{"key":"S0022481200025500_ref033","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200025500_ref015","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1969.29.351"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200025500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T20:25:24Z","timestamp":1558211124000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200025500\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,9]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1990,9]]}},"alternative-id":["S0022481200025500"],"URL":"https:\/\/doi.org\/10.2307\/2274468","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,9]]}}}