×

Strength and weakness in computable structure theory. (English) Zbl 1485.03111

Day, Adam (ed.) et al., Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 10010, 302-323 (2017).
Summary: We survey the current results about degrees of categoricity and the degrees that are low for isomorphism as well as the proof techniques used in the constructions of elements of each of these classes. We conclude with an analysis of these classes, what we may deduce about them given the sorts of proof techniques used in each case, and a discussion of future lines of inquiry.
For the entire collection see [Zbl 1352.03004].

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Anderson, B.A., Csima, B.F.: Degrees that are not degrees of categoricity. Notre Dame J. Formal Logic (to appear) · Zbl 1436.03229
[2] Ash, C.J., Knight, J.: Computable structures and the hyperarithmetical hierarchy. In: Studies in Logic and the Foundations of Mathematics, vol. 144. North-Holland (2000) · Zbl 0960.03001
[3] Csima, B.: Degrees of categoricity and related notions. In: BIRS Computable Model Theory Workshop, November 2013
[4] Csima, F.B., Franklin, J.N.Y., Shore, R.A.: Degrees of categoricity and the hyperarithmetic hierarchy. Notre Dame J. Formal Logic 54(2), 215–231 (2013) · Zbl 1311.03070
[5] Csima, B.F., Harrison-Trainor, M.: Degrees of categoricity on a cone. J. Symbolic Logic (to appear) · Zbl 1386.03049
[6] Downey, R., Griffiths, E., LaForte, G.: On Schnorr and computable randomness, martingales, and machines. Math. Log. Q. 50(6), 613–627 (2004) · Zbl 1062.68064
[7] Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity. Springer, New York (2010) · Zbl 1221.68005
[8] Ershov, Y.: A hierarchy of sets, I. Algebra Logic 7(1), 212–232 (1968). Originally appearing in Algebra i Logika 7(1), 47–74 (1968) (Russian)
[9] Ershov, Y.: On a hierarchy of sets, II. Algebra Logic 7(4), 25–43 (1968). Originally appearing in Algebra i Logika 7(4), 15–47 (1968) (Russian)
[10] Ershov, Y.: On a hierarchy of sets, III. Algebra Logic 9(1), 20–31 (1970). Originally appearing in Algebra i Logika 9(1), 34–51 (1970) (Russian) · Zbl 0233.02017
[11] Fokina, E.B., Kalimullin, I., Miller, R.: Degrees of categoricity of computable structures. Arch. Math. Logic 49(1), 51–67 (2010) · Zbl 1184.03026
[12] Franklin, J.N.Y.: Schnorr trivial reals: a construction. Arch. Math. Logic 46(7–8), 665–678 (2008) · Zbl 1142.03020
[13] Franklin, J.N.Y.: Lowness and highness properties for randomness notions. In: Arai, T. et al. (ed.) Proceedings of the 10th Asian Logic Conference, pp. 124–151. World Scientific (2010) · Zbl 1193.03072
[14] Franklin, J.N.Y., Solomon, R.: Degrees that are low for isomorphism. Computability 3(2), 73–89 (2014) · Zbl 1322.03028
[15] Franklin, J.N.Y., Stephan, F.: Schnorr trivial sets and truth-table reducibility. J. Symbol. Logic 75(2), 501–521 (2010) · Zbl 1193.03073
[16] Franklin, J.N.Y., Turetsky, D.: Genericity and lowness for isomorphism (submitted) · Zbl 1435.03068
[17] Fröhlich, A., Shepherdson, J.C.: Effective procedures in field theory. Philos. Trans. R. Soc. Lond. Ser. A. 248, 407–432 (1956) · Zbl 0070.03502
[18] Harizanov, V.S.,: Pure computable model theory. In: Handbook of Recursive Mathematics, Volume 1: Recursive Model Theory, Studies in Logic and the Foundations of Mathematics, vol. 138, pp. 3–114 (1998) · Zbl 0952.03037
[19] Hirschfeldt, D., Khoussainov, B., Shore, R., Slinko, A.: Degree spectra and computable dimensions in algebraic structures. Ann. Pure Appl. Logic 115(1–3), 71–113 (2002) · Zbl 1016.03034
[20] Hirschfeldt, D.R., Shore, R.A.: Combinatorial principles weaker than Ramsey’s theorem for pairs. J. Symbol. Logic 72(1), 171–206 (2007) · Zbl 1118.03055
[21] Hirschfeldt, D.R., Shore, R.A., Slaman, T.A.: The atomic model theorem and type omitting. Trans. Am. Math. Soc. 361(11), 5805–5837 (2009) · Zbl 1184.03005
[22] Hirschfeldt, D.R., White, W.M.: Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures. Notre Dame J. Formal Logic 43(1), 51–64 (2003). 2002 · Zbl 1048.03035
[23] Knight, J.F.: Degrees coded in jumps of orderings. J. Symbol. Logic 51(4), 1034–1042 (1986) · Zbl 0633.03038
[24] Marker, D.: Non \[ \Sigma _n \] axiomatizable almost strongly minimal theories. J. Symbol. Logic 54(3), 921–927 (1989) · Zbl 0698.03021
[25] Montalbán, A.: Priority arguments via true stages. J. Symbol. Log. 79(4), 1315–1335 (2014) · Zbl 1353.03050
[26] Moschovakis, Y.N.: Descriptive Set Theory. Studies in Logic and the Foundations of Mathematics, vol. 100. North-Holland (1980) · Zbl 0433.03025
[27] Nies, A.: Computability and Randomness. Clarendon Press, Oxford (2009) · Zbl 1237.03027
[28] Nies, A., Stephan, F., Terwijn, S.A.: Randomness, relativization and Turing degrees. J. Symbol. Logic 70(2), 515–535 (2005) · Zbl 1090.03013
[29] Odifreddi, P.: Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics, vol. 125. North-Holland (1989) · Zbl 0661.03029
[30] Odifreddi, P.: Classical Recursion Theory, Volume II. Studies in Logic and the Foundations of Mathematics, vol. 143. North-Holland (1999) · Zbl 0931.03057
[31] Sacks, G.E.: Higher Recursion Theory. Springer, New York (1990) · Zbl 0716.03043
[32] Slaman, T.A., Solovay, R.M.: When oracles do not help. In: Fourth Annual Workshop on Computational Learning Theory, pp. 379–383. Morgan Kaufman, Los Altos (1991)
[33] Soare, R.: The Friedberg-Muchnik theorem re-examined. Can. J. Math. 24, 1070–1078 (1972) · Zbl 0225.02028
[34] Soare, R.I.: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer, New York (1987)
[35] Suggs, J.: Degrees that are low for \[ \mathcal{C} \] isomorphism. Ph.D. thesis, University of Connecticut (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.