Algebra i logika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Algebra Logika: Year: Volume: Issue: Page: Find

 Algebra Logika, 2002, Volume 41, Number 6, Pages 639–681 (Mi al201)

Computable Structure and Non-Structure Theorems

S. S. Goncharova, J. F. Knightb

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b University of Notre Dame

Abstract: In a lecture in Kazan (1977), Goncharov dubbed a number of problems regarding the classification of computable members of various classes of structures. Some of the problems seemed likely to have nice answers, while others did not. At the end of the lecture, Shore asked what would be a convincing negative result. The goal of the present article is to consider some possible answers to Shore's question. We consider structures $\mathcal A$ of some computable language, whose universes are computable sets of constants. In measuring complexity, we identify $\mathcal A$ with its atomic diagram $D(\mathcal A)$, which, via the Gödel numbering, may be treated as a subset of $\omega$. In particular, $\mathcal A$ is computable if $D(\mathcal A)$ is computable. If $K$ is some class, then $K^c$ denotes the set of computable members of $K$. A computable characterization for $K$ should separate the computable members of $K$ from other structures, that is, those that either are not in $K$ or are not computable. A computable classification (structure theorem) should describe each member of $K^c$ up to isomorphism, or other equivalence, in terms of relatively simple invariants. A computable non-structure theorem would assert that there is no computable structure theorem. We use three approaches. They all give the “correct” answer for vector spaces over $Q$, and for linear orderings. Under all of the approaches, both classes have a computable characterization, and there is a computable classification for vector spaces, but not for linear orderings. Finally, we formulate some open problems.

Full text: PDF file (4044 kB)
References: PDF file   HTML file

English version:
Algebra and Logic, 2002, 41:6, 351–373

Bibliographic databases:

UDC: 510.53

Citation: S. S. Goncharov, J. F. Knight, “Computable Structure and Non-Structure Theorems”, Algebra Logika, 41:6 (2002), 639–681; Algebra and Logic, 41:6 (2002), 351–373

Citation in format AMSBIB
\Bibitem{GonKni02} \by S.~S.~Goncharov, J.~F.~Knight \paper Computable Structure and Non-Structure Theorems \jour Algebra Logika \yr 2002 \vol 41 \issue 6 \pages 639--681 \mathnet{http://mi.mathnet.ru/al201} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1967769} \zmath{https://zbmath.org/?q=an:1034.03044} \transl \jour Algebra and Logic \yr 2002 \vol 41 \issue 6 \pages 351--373 \crossref{https://doi.org/10.1023/A:1021758312697} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33750733406} 

• http://mi.mathnet.ru/eng/al201
• http://mi.mathnet.ru/eng/al/v41/i6/p639

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. White WM, “On the complexity of categoricity in computable structures”, Mathematical Logic Quarterly, 49:6 (2003), 603–614
2. Goncharov SS, Harizanov VS, Knight JF, et al, “Pi(1)(1) relations and paths through O”, Journal of Symbolic Logic, 69:2 (2004), 585–611
3. Calvert W, “The isomorphism problem for classes of computable fields”, Archive For Mathematical Logic, 43:3 (2004), 327–336
4. Khoussainov B., Nies A., Rubin S., Stephan F., “Automatic structures: Richness and limitations”, 19th Annual IEEE Symposium on Logic in Computer Science, Proceedings, Proceedings/Symposium on Logic in Computer Science, 2004, 44–53
5. Calvert W., “The isomorphism problem for computable Abelian p-groups of bounded length”, Journal of Symbolic Logic, 70:1 (2005), 331–345
6. W. Calvert, V. S. Harizanova, J. F. Knight, S. Miller, “Index sets of computable structures”, Algebra and Logic, 45:5 (2006), 306–325
7. N. T. Kogabaev, “Complexity of some natural problems on the class of computable $I$-algebras”, Siberian Math. J., 47:2 (2006), 291–297
8. N. S. Vinokurov, “Index sets of classes of automatic structures”, Siberian Math. J., 47:5 (2006), 835–843
9. Calvert W., Knight J.F., “Classification from a computable viewpoint”, Bulletin of Symbolic Logic, 12:2 (2006), 191–218
10. Calvert W., Knight J.F., Millar J., “Computable trees of Scott rank omega(CK)(1), and computable approximation”, Journal of Symbolic Logic, 71:1 (2006), 283–298
11. E. B. Fokina, “Index sets of decidable models”, Siberian Math. J., 48:5 (2007), 939–948
12. Khoussainov B., Nies A., Rubin S., Stephan F., “Automatic Structures: Richness and Limitations”, Logical Methods in Computer Science, 3:2 (2007), 2
13. Calvert W., Fokina E., Goncharov S.S., Knight J.F., Kudinov O., Morozov A.S., Puzarenko V., “Index sets for classes of high rank structures”, Journal of Symbolic Logic, 72:4 (2007), 1418–1432
14. Calvert W., Goncharov S.S., Knight J.F., “Computable structures of Scott rank omega(CK)(1) in familiar classes”, Advances in Logic, Contemporary Mathematics Series, 425, 2007, 49–66
15. Fokina E.B., “Index sets of computable structures with decidable theories”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 290–296
16. E. N. Pavlovskii, “Estimation of the algorithmic complexity of classes of computable models”, Siberian Math. J., 49:3 (2008), 512–523
17. Downey R., Montalban A., “The isomorphism problem for torsion-free Abelian groups is analytic complete”, Journal of Algebra, 320:6 (2008), 2291–2300
18. Rubin S., “Automata presenting structures: A survey of the finite string case”, Bulletin of Symbolic Logic, 14:2 (2008), 169–209
19. Greenberg N., Montalban A., “Ranked structures and arithmetic transfinite recursion”, Transactions of the American Mathematical Society, 360:3 (2008), 1265–1307
20. E. N. Pavlovskii, “Indeksnye mnozhestva prostykh modelei”, Sib. elektron. matem. izv., 5 (2008), 200–210
21. Khoussainov B., Minnes M., “Model theoretic complexity of automatic structures - (Extended abstract)”, Theory and Applications of Models of Computation, Proceedings, Lecture Notes in Computer Science, 4978, 2008, 514–525
22. E. N. Pavlovskii, “Slozhnost indeksnykh mnozhestv nekotorykh klassov modelei”, Vestn. NGU. Ser. matem., mekh., inform., 8:1 (2008), 71–76
23. E. B. Fokina, “Algoritmicheskie svoistva modelei signatury s dvumya odnomestnymi funktsionalnymi simvolami”, Vestn. NGU. Ser. matem., mekh., inform., 8:1 (2008), 90–101
24. S. S. Goncharov, N. T. Kogabaev, “O $\Sigma^0_1$-klassifikatsii otnoshenii na vychislimykh strukturakh”, Vestn. NGU. Ser. matem., mekh., inform., 8:4 (2008), 23–32
25. Khoussainov B., Minnes M., “Model-theoretic complexity of automatic structures”, Annals of Pure and Applied Logic, 161:3 (2009), 416–426
26. Fokina E.B., “Index sets for some classes of structures”, Annals of Pure and Applied Logic, 157:2–3 (2009), 139–147
27. Fokina E.B., Friedman S.-D., “Equivalence Relations on Classes of Computable Structures”, Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, 5635, 2009, 198–207
28. Kuske D., Liu J., Lohrey M., “The Isomorphism Problem On Classes of Automatic Structures”, 25th Annual IEEE Symposium on Logic in Computer Science (LICS 2010), IEEE Symposium on Logic in Computer Science, 2010, 160–169
29. Kuske D., Liu J., Lohrey M., “The Isomorphism Problem for omega-Automatic Trees”, Computer Science Logic, Lecture Notes in Computer Science, 6247, 2010, 396–410
30. Melnikov A.G., “Computable Ordered Abelian Groups and Fields”, Programs, Proofs, Processes, Lecture Notes in Computer Science, 6158, 2010, 321–330
31. S. S. Goncharov, “Degrees of autostability relative to strong constructivizations”, Proc. Steklov Inst. Math., 274 (2011), 105–115
32. J. Carson, E. Fokina, V. S. Harizanov, J. F. Knight, S. Quinn, C. Safranski, J. Wallbaum, “The computable embedding problem”, Algebra and Logic, 50:6 (2012), 478–493
33. Fokina E.B., Friedman S.-D., “On S11 equivalence relations over the natural numbers”, MLQ Math Log Q, 58:1–2 (2012), 113–124
34. Fokina E.B. Friedman S.-D. Harizanov V. Knight J.F. McCoy Ch. Montalban A., “Isomorphism Relations on Computable Structures”, J. Symb. Log., 77:1 (2012), 122–132
35. N. T. Kogabaev, “The complexity of isomorphism problem for computable projective planes”, J. Math. Sci., 203:4 (2014), 509–515
36. Kuske D., Liu J., Lohrey M., “The Isomorphism Problem for Omega-Automatic Trees”, Ann. Pure Appl. Log., 164:1 (2013), 30–48
37. S. S. Goncharov, “Index Sets of Almost Prime Constructive Models”, J. Math. Sci., 205:3 (2015), 355–367
38. N. A. Bazhenov, “Computable numberings of the class of Boolean algebras with distinguished endomorphisms”, Algebra and Logic, 52:5 (2013), 355–366
39. S. S. Goncharov, M. I. Marchuk, “Index Sets of Autostable Relative to Strong Constructivizations Constructive Models”, J. Math. Sci., 205:3 (2015), 368–388
40. Montalban A., “Copyable Structures”, J. Symb. Log., 78:4 (2013), 1199–1217
41. Becker H., “Isomorphism of Computable Structures and Vaught's Conjecture”, J. Symb. Log., 78:4 (2013), 1328–1344
42. M. V. Dorzhieva, “Eliminatsiya metarekursii iz teoremy Ouinsa”, Vestn. NGU. Ser. matem., mekh., inform., 14:1 (2014), 35–43
43. Melnikov A.G., “Computable Abelian Groups”, Bull. Symb. Log., 20:3 (2014), 315–356
44. Fokina E.B. Harizanov V. Melnikov A., “Computable Model Theory”, Turing'S Legacy: Developments From Turing'S Ideas in Logic, Lecture Notes in Logic, 42, ed. Downey R., Cambridge Univ Press, 2014, 124–194
45. S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of Boolean algebras autostable relative to strong constructivizations”, Siberian Math. J., 56:3 (2015), 393–404
46. S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations”, Algebra and Logic, 54:2 (2015), 108–126
47. S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of linear orderings that are autostable relative to strong constructivizations”, J. Math. Sci., 221:6 (2017), 840–848
48. S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations”, Algebra and Logic, 54:6 (2016), 428–439
49. Calvert W., “Pac Learning, Vc Dimension, and the Arithmetic Hierarchy”, Arch. Math. Log., 54:7-8 (2015), 871–883
50. Goncharov S.S. Bazhenov N.A. Marchuk M.I., “Index Sets of Autostable Relative To Strong Constructivizations Constructive Models For Familiar Classes”, Dokl. Math., 92:2 (2015), 525–527
51. Goncharov S.S., Marchuk M.I., “Index Sets of Constructive Models of Nontrivial Signature Autostable Relative To Strong Constructivizations”, Dokl. Math., 91:2 (2015), 158–159
52. N. A. Bazhenov, “Degrees of autostability relative to strong constructivizations for Boolean algebras”, Algebra and Logic, 55:2 (2016), 87–102
53. N. A. Bazhenov, “Degrees of autostability for linear orderings and linearly ordered Abelian groups”, Algebra and Logic, 55:4 (2016), 257–273
54. M. I. Marchuk, “Index set of structures with two equivalence relations that are autostable relative to strong constructivizations”, Algebra and Logic, 55:4 (2016), 306–314
55. Miller R. Ng K.M., “Finitary Reducibility on Equivalence Relations”, J. Symb. Log., 81:4 (2016), 1225–1254
56. Downey R.G., Melnikov A.G., Ng K.M., “A Friedberg Enumeration of Equivalence Structures”, J. Math. Log., 17:2 (2017), UNSP 1750008
57. S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of the groups autostable relative to strong constructivizations”, Siberian Math. J., 58:1 (2017), 72–77
58. Melnikov A.G., “Torsion-Free Abelian Groups With Optimal Scott Families”, J. Math. Log., 18:1 (2018)
59. Knight J.F. Saraph V., “Scott Sentences For Certain Groups”, Arch. Math. Log., 57:3-4 (2018), 453–472
60. Melnikov A.G. Ng K.M., “Computable Torsion Abelian Groups”, Adv. Math., 325 (2018), 864–907
61. Lange K. Miller R. Steiner R.M., “Classifications of Computable Structures”, Notre Dame J. Form. Log., 59:1 (2018), 35–59
62. A. K. Voǐtov, “The $\Delta^0_\alpha$-computable enumerations of the classes of projective planes”, Siberian Math. J., 59:2 (2018), 252–263
63. N. T. Kogabaev, “Complexity of the isomorphism problem for computable free projective planes of finite rank”, Siberian Math. J., 59:2 (2018), 295–308
64. Harrison-Trainor M., “There Is No Classification of the Decidably Presentable Structures”, J. Math. Log., 18:2 (2018), UNSP 1850010
65. M. V. Dorzhieva, “Odnoznachnaya numeratsiya dlya semeistva vsekh $\Sigma^{1}_{2}$-mnozhestv”, Sib. zhurn. chist. i prikl. matem., 18:2 (2018), 47–52
66. S. Boyadzhiyska, K. Lange, A. Raz, R. Scanlon, J. Wallbaum, X. Zhang, “Classifications of definable subsets”, Algebra and Logic, 58:5 (2019), 383–404
67. M. V. Zubkov, I. Sh. Kalimullin, A. G. Mel'nikov, A. N. Frolov, “Punctual copies of algebraic structures”, Siberian Math. J., 60:6 (2019), 993–1002
68. Bazhenov N. Harrison-Trainor M. Kalimullin I. Melnikov A. Ng K.M., “Automatic and Polynomial-Time Algebraic Structures”, J. Symb. Log., 84:4 (2019), 1630–1669
69. Mahmoud M.A., “Degrees of Categoricity of Trees and the Isomorphism Problem”, Math. Log. Q., 65:3 (2019), 293–304
70. Downey R. Melnikov A. Ng K.M., “Categorical Linearly Ordered Structures”, Ann. Pure Appl. Log., 170:10 (2019), 1243–1255
71. Miller R., “Isomorphism and Classification For Countable Structures”, Computability, 8:2 (2019), 99–117
72. Quinn S.B., “Scott Sentences For Equivalence Structures”, Arch. Math. Log., 59:3-4 (2020), 453–460
73. M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh uporyadochennykh abelevykh grupp”, Matem. tr., 23:1 (2020), 169–176
74. N. Bazhenov, M. Marchuk, “A note on decidable categoricity and index sets”, Sib. elektron. matem. izv., 17 (2020), 1013–1026
75. Harrison-Trainor M., Melnikov A., Ng K.M., “Computability of Polish Spaces Up to Homeomorphism”, J. Symb. Log., 85:4 (2020), 1664–1686
76. Bazhenov N. Fokina E. San Mauro L., “Learning Families of Algebraic Structures From Informant”, Inf. Comput., 275 (2020), 104590
77. Downey R., Melnikov A., Ng K.M., “Enumerating Abelian P-Groups”, J. Algebra, 560 (2020), 745–790
78. Brown T.A. Mcnicholl T.H. Melnikov A.G., “on the Complexity of Classifying Lebesgue Spaces”, J. Symb. Log., 85:3 (2020), PII S0022481220000638, 1254–1288
79. Downey R. Harrison-Trainor M. Kalimullin I. Melnikov A. Turetsky D., “Graphs Are Not Universal For Online Computability”, J. Comput. Syst. Sci., 112 (2020), 1–12
80. Bazhenov N. Goncharov S. Melnikov A., “Decompositions of Decidable Abelian Groups”, Int. J. Algebr. Comput., 30:1 (2020), 49–90
•  Number of views: This page: 646 Full text: 222 References: 48 First page: 1