Bulletin of the American Mathematical Society

Author(s): Piergiorgio Odifreddi
Journal: Bull. Amer. Math. Soc. 4 (1981), 37-86.
MSC (1980): Primary 03D30; Secondary 03D25
MathSciNet review: 590818
Retrieve article in: PDF

[Be] O. V. Belegradek, m-degrees of the word problem, Sibirsk Math. J. 19 (1978), 867-870. MR 515176

[Co] P. F. Cohen, Weak truth-table reducibility and the pointwise ordering of 1-1 recursive functions, Doctoral Dissertation, Univ. of Illinois, Urbana, Illinois, 1975.

[Da1] M. Davis, The undecidable, Raven Press, New York, 1965. MR 189996

[Da2] M. Davis, Unsolvable problems, Handbook of Math. Logic (Barwise, ed.), North-Holland Amsterdam, 1977, pp. 567-594. MR 457132

[Deg1] A. N. Degtev, Remarks on retraceable, regressive, and pointwise-decomposable sets, Algebra and Logic 9 (1970), 390-395. MR 286651

[Deg2] A. N. Degtev, Hypersimple sets with retraceable complements, Algebra and Logic 10 (1971), 147-154. MR 288023

[Deg3] A. N. Degtev, m-powers of simple sets, Algebra and Logic 11 (1972), 74-80.

[Deg4] A. N. Degtev, Hereditary sets and tabular reducibility, Algebra and Logic 11 (1972), 145-152.

[Deg5] A. N. Degtev, tt- and m-degrees, Algebra and Logic 12 (1973), 78-89. MR 424545

[Deg6] A. N. Degtev, Partially ordered sets of 1-degrees, contained in recursively enumerable m-degrees, Algebra and Logic 15 (1976), 153-164. MR 537543

[Deg7] A. N. Degtev, On minimal 1-degrees and tt-reducibility, Sibirsk. Math. Z. 17 (1976), 1014-1022. (Russian) MR 422004

[Deg8] A. N. Degtev, On m-degrees of supersets of simple sets, Mat. Zametki 23 (1978), 889-893. (Russian) MR 502057

[Deg9] A. N. Degtev, Three theorems on tt-degrees, Algebra i Logic 17 (1978), 270-281. (Russian) MR 538297

[Den1] S. D. Denisov, On m-degrees of recursively enumerable sets, Algebra and Logic 9 (1970), 254-256. MR 286652

[Den2] A. N. Degtev, Three theorems on elementary theories and tt-reducibility, Algebra and Logic 13 (1974), 1-2.

[Dek] J. C. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791-796. MR 63995

[E1] Y. L. Ershov, Hyperhypersimple m-degrees, Algebra and Logic 8 (1969), 298-315. MR 280368

[E2] Y. L. Ershov, On inseparable pairs, Algebra and Logic 9 (1970), 396-399. MR 286653

[E3] Y. L. Ershov, Positive equivalences, Algebra and Logic 10 (1971), 378-394. MR 307896

[E4] Y. L. Ershov, The upper semilattice of numerations of a finite set, Algebra and Logic 14 (1975), 159-175. MR 416884

[EL] Y. L. Ershov and I. A. Lavrov, The upper semilattice L(γ), Algebra and Logic 12 (1973), 93-106. MR 409148

[ELTT] Y. L. Ershov et al., Elementary theories, Russian Math. Surveys 20 (1965), 35-105. MR 186553

[FeR] J. Ferrante and C. W. Rackoff, Computational complexity of logical theories, Lecture Notes in Math., vol. 718, Springer-Verlag, Berlin and New York, 1979. MR 537764

[Fr] R. 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

[Go] R. L. Goodstein, Recursive analysis, North-Holland, Amsterdam, 1961. MR 131974

[Hi] P. G. Hinman, Recursion-theoretic hierarchies, Springer, 1978. MR 499205

[J1] C. G. Jockusch, Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420-436. MR 220595

[J2] C. G. Jockusch, Jr., Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229-237. MR 245439

[J3] C. G. Jockusch, Jr., Degrees in which the recursive sets are uniformly recursive, Canad. J. Math. 24 (1972), 1092-1099. MR 321716

[JSo] C. G. Jockusch, Jr. and R. I. Soare, Post's problem and his hypersimple set, J. Symbolic Logic 38 (1973), 446-452. MR 337544

[Ka1] S. Kallibekov, Index sets of degrees of unsolvability, Algebra and Logic 10 (1971), 198-204. MR 294129

[Ka2] S. Kallibekov, On degrees of recursively enumerable sets, Sibirsk. Math. J. 14 (1973), 290-293. MR 329876

[Ka3] S. Kallibekov, Truth tabular degrees of recursively enumerable sets, Math. Notes 14 (1973), 958-961. MR 329876

[KM] A. S. Kechris and D. A. Martin, Infinite games and effective descriptive set theory, Proc. of London Conf. on Analytic Sets, 1978.

[Ko1] G. N. Kobzev, btt-reducibility, Algebra and Logic 12 (1973), 107-115. MR 401447

[Ko2] G. N. Kobzev, On btt-reducibility. II, Algebra and Logic 12 (1973), 242-248. MR 401447

[Ko3] G. N. Kobzev, On r-separable sets (preprint).

[Ko4] G. N. Kobzev, On tt-degrees of r.e. T-degrees, Mat. Sb. 106 (1978), 507-514. (Russian) MR 507813

[Ko5] G. N. Kobzev, On the semilattice of tt-degrees, Bull. Acad. Sci. Georgian SSR 90 (1978). (Russian) MR 514301

[Ko6] G. N. Kobzev, Recursively enumerable bw-degrees, Math. Notes Acad. Sci. USSR 21 (1977), 473-477. MR 465827

[Ku] G. L. Kurdjumov, An algorithm-theoretic method of studying homogeneous random media, Soviet Math. Dokl. 19 (1978), 166-171. MR 483738

[La1] A. H. Lachlan, A note on universal sets, J. Symbolic Logic 31 (1966), 573-574. MR 211857

[La2] A. H. Lachlan, Initial segments of one-one degrees, Pacific J. Math. 29 (1969), 351-366. MR 260591

[La3] A. H. Lachlan, Initial segments of many-one degrees, Canad J. Math. 22 (1970), 75-85. MR 256875

[La4] A. H. Lachlan, Solution to a problem of Spector, Canad J. Math. 23 (1971), 247-256. MR 317911

[La5] A. H. Lachlan, Recursively enumerable many-one degrees, Algebra and Logic 11 (1972), 186-202. MR 309721

[La6] A. H. Lachlan, Two theorems on many-one degrees of recursively enumerable sets, Algebra and Logic 11 (1972), 127-132. MR 309720

[La7] A. H. Lachlan, wtt-complete sets are not necessarily tt-complete, Proc. Amer. Math. Soc. 48 (1975), 429-434. MR 357087

[La8] A. H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 8 (1975), 307-365. MR 409150

[LL] A. H. Lachlan and R. Lebeuf, Countable initial segments of the degrees of unsolvability, J. Symbolic Logic 41 (1976), 289-300. MR 403937

[Lad] R. E. Ladner, On the structure of polynomial time reducibilities, J. Assoc. Comput. Mach. 22 (1975), 155-171. MR 464698

[LS] R. E. Ladner and L. P. Sasso, The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), 429-448. MR 379157

[Le] M. Lerman, Turing degrees and many-one degrees of maximal sets, J. Symbolic Logic 35 (1970), 29-40. MR 278948

[Ma1] S. S. Marchenkov, The existence of recursively enumerable minimal truth-table degrees, Algebra and Logic 14 (1975), 257-261. MR 409151

[Ma2] S. S. Marchenkov, On the congruence of the upper semilattices of recursively enumerable m-powers and tabular powers, Math. Notes Acad. Sci. USSR 20 (1976), 567-570.

[Ma3] S. S. Marchenkov, Tabular powers of maximal sets, Math. Notes Acad. Sci. USSR 20 (1976), 766-770.

[Ma4] S. S. Marchenkov, One class of partial sets, Math. Notes Acad. Sci. USSR 20 (1976), 823-825.

[Mt1] D. A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), 363-371. MR 403976

[Mt2] D. A. Martin, Descriptive set theory, Handbook of Math. Logic, (Barwise (ed.)), North-Holland, Amsterdam, 1977, pp. 783-815.

[MPE] D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205-209. MR 280374

[MN] G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), 289-320. MR 556895

[Mi] D. P. Miller, Ph. D. dissertation, University of Chicago, 1981.

[MM] W. Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlag Math. 14 (1968), 159-166. MR 228341

[McL] T. G. McLaughlin, A theorem on intermediate reducibilities, Proc. Amer. Math. Soc. 19 (1968), 87-90. MR 219420

[NS] A. Nerode and R. A. Shore, Second order logic and first order theories of reducibility ordering, Proc. of Kleene Symposium, North-Holland, New York (to appear). MR 591882

[O] P. G. Odifreddi, Classical recursion theory (to appear).

[Po] E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284-316. MR 10514

[PE] M. B. Pour-El, Effectively extensible theories, J. Symbolic Logic 33 (1968), 56-68. MR 234834

[Ro] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 224462

[Ru] J. M. Rubin, Ph.D. dissertation, Univ. Calif., Berkeley, 1981.

[Sh] J. R. Shoenfield, Undecidable and creative theories, Fund. Math. 49 (1961), 171-179. MR 130177

[So1] R. I. Soare, Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978), 1149-1181. MR 508451

[So2] R. I. Soare, Constructions in the recursively enumerable degrees, CIME Summer School, Bressanone (Italy), 1979 (to appear).

[S1] V. D. Solove'v, Q-reducibility and hyperhypersimple sets, Prob. Meth. and Cybern. 10-11 (1974), 121-128. (Russian) MR 476454

[V] V. V. V'yugin, Segments of recursively enumerable m-degrees, Algebra and Logic 13 (1974), 361-373. MR 401449

[Y1] C. E. M. Yates, Three theorems on the degree of recursively enumerable sets, Duke Math. J. 32 (1965), 461-468. MR 180486

[Y2] C. E. M. Yates, On the degrees of index sets, Trans. Amer. Math. Soc. 121 (1966), 309-328. MR 184855

[Y3] C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249-266. MR 241295

[Yo] P. R. Young, Linear orderings under one-one reducibility, J. Symbolic Logic 31 (1966), 70-85. MR 231720

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1980): 03D30, 03D25

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS