Strong reducibilities

Odifreddi, Piergiorgio

doi:10.1090/S0273-0979-1981-14863-1

Strong reducibilities
HTML articles powered by AMS MathViewer

by Piergiorgio Odifreddi PDF

Bull. Amer. Math. Soc. 4 (1981), 37-86

References

O. V. Belegradek, $m$-degrees of the word problem, Sibirsk. Mat. Zh. 19 (1978), no. 6, 1232–1236, 1436 (Russian). MR 515176
Martin Davis (ed.), The undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions, Raven Press, Hewlett, N.Y., 1965. MR 0189996
Handbook of mathematical logic, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland Publishing Co., Amsterdam, 1977. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra. MR 457132
A. N. Degtev, Several remarks on retraceable, regressive and pointwise decomposable sets, Algebra i Logika 9 (1970), 651–660 (Russian). MR 0286651
A. N. Degtev, Hypersimple sets with retraceable complements, Algebra i Logika 10 (1971), 235–246 (Russian). MR 0288023
A. N. Dëgtev, $tt$- and $m$-degrees, Algebra i Logika 12 (1973), 143–161, 243 (Russian). MR 0424545
A. N. Degtëv, Partially ordered sets of $1$-degrees that occur in recursively enumerable $m$-degrees, Algebra i Logika 15 (1976), no. 3, 249–266, 365 (Russian). MR 0537543
A. N. Dëgtev, Minimal $1$-degrees, and truth-table reducibility, Sibirsk. Mat. Ž. 17 (1976), no. 5, 1014–1022, 1196 (Russian). MR 0422004
A. N. Dëgtev, m-degrees of supersets of simple sets, Mat. Zametki 23 (1978), no. 6, 889–893 (Russian). MR 502057
A. N. Dëgtev, Three theorems on $tt$-degrees, Algebra i Logika 17 (1978), no. 3, 270–281, 357–358 (Russian). MR 538297
S. D. Denisov, The $m$-degrees of recursively enumerable sets, Algebra i Logika 9 (1970), 422–427 (Russian). MR 0286652
J. C. E. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791–796. MR 63995, DOI 10.1090/S0002-9939-1954-0063995-6
Ju. L. Eršov, Hyperhypersimple $m$-degrees, Algebra i Logika 8 (1969), 523–552 (Russian). MR 0280368
Ju. L. Eršov, Inseparable pairs, Algebra i Logika 9 (1970), 661–666 (Russian). MR 0286653
Ju. L. Eršov, Positive equivalences, Algebra i Logika 10 (1971), 620–650 (Russian). MR 0307896
Ju. L. Eršov, The upper semilattice of numerations of a finite set, Algebra i Logika 14 (1975), no. 3, 258–284, 368 (Russian). MR 0416884
Ju. L. Eršov and I. A. Lavrov, The upper semilattice $L(\gamma )$, Algebra i Logika 12 (1973), 167–189, 243–244 (Russian). MR 0409148
Ju. L. Eršov, I. A. Lavrov, A. D. Taĭmanov, and M. A. Taĭclin, Elementary theories, Uspehi Mat. Nauk 20 (1965), no. 4 (124), 37–108 (Russian). MR 0186553
Jeanne Ferrante and Charles W. Rackoff, The computational complexity of logical theories, Lecture Notes in Mathematics, vol. 718, Springer, Berlin, 1979. MR 537764, DOI 10.1007/BFb0062837
Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309–316. MR 109125, DOI 10.2307/2964290
R. L. Goodstein, Recursive analysis, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1961. MR 0131974
Peter G. Hinman, Recursion-theoretic hierarchies, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1978. MR 499205, DOI 10.1007/978-3-662-12898-5
Carl G. Jockusch Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420–436. MR 220595, DOI 10.1090/S0002-9947-1968-0220595-7
Carl G. Jockusch Jr., Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229–237. MR 245439, DOI 10.1090/S0002-9947-1969-0245439-X
Carl G. Jockusch Jr., Degrees in which the recursive sets are uniformly recursive, Canadian J. Math. 24 (1972), 1092–1099. MR 321716, DOI 10.4153/CJM-1972-113-9
Carl G. Jockusch Jr. and Robert I. Soare, Post’s problem and his hypersimple set, J. Symbolic Logic 38 (1973), 446–452. MR 337544, DOI 10.2307/2273042
S. Kallibekov, Index sets of degrees of unsolvability, Algebra i Logika 10 (1971), 316–326 (Russian). MR 0294129
S. Kallibekov, The degrees of recursively enumerable sets, Sibirsk. Mat. Ž. 14 (1973), 421–426, 463 (Russian). MR 0329876
S. Kallibekov, The degrees of recursively enumerable sets, Sibirsk. Mat. Ž. 14 (1973), 421–426, 463 (Russian). MR 0329876
G. N. Kobzev, btt-reducibility. I, II, Algebra i Logika 12 (1973), 190–204, 244; ibid. 12 (1973), 433–444, 492 (Russian). MR 0401447
G. N. Kobzev, btt-reducibility. I, II, Algebra i Logika 12 (1973), 190–204, 244; ibid. 12 (1973), 433–444, 492 (Russian). MR 0401447
G. N. Kobzev, The semilattice of tt-degrees, Sakharth. SSR Mecn. Akad. Moambe 90 (1978), no. 2, 281–283 (Russian, with English and Georgian summaries). MR 514301
G. N. Kobzev, The semilattice of tt-degrees, Sakharth. SSR Mecn. Akad. Moambe 90 (1978), no. 2, 281–283 (Russian, with English and Georgian summaries). MR 514301
G. N. Kobzev, Recursively enumerable $bw$-degrees, Mat. Zametki 21 (1977), no. 6, 839–846 (Russian). MR 465827
G. L. Kurdjumov, An algorithm-theoretic method for the study of homogeneous random media, Dokl. Akad. Nauk SSSR 238 (1978), no. 5, 1047–1050 (Russian). MR 483738
A. H. Lachlan, A note on universal sets, J. Symbolic Logic 31 (1966), 573–574. MR 211857, DOI 10.2307/2269692
A. H. Lachlan, Initial segments of one-one degrees, Pacific J. Math. 29 (1969), 351–366. MR 260591, DOI 10.2140/pjm.1969.29.351
A. H. Lachlan, Initial segments of many-one degrees, Canadian J. Math. 22 (1970), 75–85. MR 256875, DOI 10.4153/CJM-1970-010-6
A. H. Lachlan, Solution to a problem of Spector, Canadian J. Math. 23 (1971), 247–256. MR 317911, DOI 10.4153/CJM-1971-024-7
A. H. Lachlan, Recursively enumerable many-one degrees, Algebra i Logika 11 (1972), 326–358, 362. MR 0309721
A. H. Lachlan, Two theorems of many-one degrees of recursively enumerable sets, Algebra i Logika 11 (1972), 216–229, 239. MR 0309720
A. H. Lachlan, $\textrm {wtt}$-complete sets are not necessarily $\textrm {tt}$-complete, Proc. Amer. Math. Soc. 48 (1975), 429–434. MR 357087, DOI 10.1090/S0002-9939-1975-0357087-X
Alistair H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1976), no. 4, 307–365. MR 409150, DOI 10.1016/0003-4843(76)90016-4
A. H. Lachlan and R. Lebeuf, Countable initial segments of the degrees of unsolvability, J. Symbolic Logic 41 (1976), no. 2, 289–300. MR 403937, DOI 10.2307/2272227
Richard E. Ladner, On the structure of polynomial time reducibility, J. Assoc. Comput. Mach. 22 (1975), 155–171. MR 464698, DOI 10.1145/321864.321877
Richard E. Ladner and Leonard P. Sasso Jr., The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), no. 4, 429–448. MR 379157, DOI 10.1016/0003-4843(75)90007-8
Manuel Lerman, Turing degrees and many-one degrees of maximal sets, J. Symbolic Logic 35 (1970), 29–40. MR 278948, DOI 10.2307/2271152
S. S. Marčenkov, The existence of recursively enumerable minimal truth-table degrees, Algebra i Logika 14 (1975), no. 4, 422–429 (Russian). MR 0409151
Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205–209. MR 280374, DOI 10.2307/2270510
G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289–320. MR 556895, DOI 10.1016/0003-4843(79)90011-1
Webb Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159–166. MR 228341, DOI 10.1002/malq.19680140704
T. G. McLaughlin, A theorem on intermediate reducibilities, Proc. Amer. Math. Soc. 19 (1968), 87–90. MR 219420, DOI 10.1090/S0002-9939-1968-0219420-5
Anil Nerode and Richard A. Shore, Second order logic and first order theories of reducibility orderings, The Kleene Symposium (Proc. Sympos., Univ. Wisconsin, Madison, Wis., 1978), Studies in Logic and the Foundations of Mathematics, vol. 101, North-Holland, Amsterdam-New York, 1980, pp. 181–200. MR 591882
Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
Marian Boykan Pour-El, Effectively extensible theories, J. Symbolic Logic 33 (1968), 56–68. MR 234834, DOI 10.2307/2270052
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
J. R. Shoenfield, Undecidable and creative theories, Fund. Math. 49 (1960/61), 171–179. MR 130177, DOI 10.4064/fm-49-2-171-179
Robert I. Soare, Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. MR 508451, DOI 10.1090/S0002-9904-1978-14552-2
V. D. Solov′ev, $Q$-reducibility, and hyperhypersimple sets, Probabilistic methods and cybernetics, No. X-XI (Russian), Izdat. Kazan. Univ., Kazan, 1974, pp. 121–128. MR 0476454
V. V. V′jugin, Segments of recursively enumerable $m$-degrees, Algebra i Logika 13 (1974), no. 6, 635–654, 719 (Russian). MR 0401449
C. E. M. Yates, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468. MR 180486
C. E. M. Yates, On the degrees of index sets, Trans. Amer. Math. Soc. 121 (1966), 309–328. MR 184855, DOI 10.1090/S0002-9947-1966-0184855-9
C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249–266. MR 241295, DOI 10.1090/S0002-9947-1969-0241295-4
Paul R. Young, Linear orderings under one-one reducibility, J. Symbolic Logic 31 (1966), 70–85. MR 231720, DOI 10.2307/2270621