Algebra i logika
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Algebra Logika:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 80 scientific papers (total in 80 papers)

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 Gö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
Received: 08.03.2001

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
\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
\jour Algebra and Logic
\yr 2002
\vol 41
\issue 6
\pages 351--373

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    3. Calvert W, “The isomorphism problem for classes of computable fields”, Archive For Mathematical Logic, 43:3 (2004), 327–336  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  isi
    5. Calvert W., “The isomorphism problem for computable Abelian p-groups of bounded length”, Journal of Symbolic Logic, 70:1 (2005), 331–345  crossref  mathscinet  zmath  isi  scopus
    6. W. Calvert, V. S. Harizanova, J. F. Knight, S. Miller, “Index sets of computable structures”, Algebra and Logic, 45:5 (2006), 306–325  mathnet  crossref  mathscinet  zmath
    7. N. T. Kogabaev, “Complexity of some natural problems on the class of computable $I$-algebras”, Siberian Math. J., 47:2 (2006), 291–297  mathnet  crossref  mathscinet  zmath  isi
    8. N. S. Vinokurov, “Index sets of classes of automatic structures”, Siberian Math. J., 47:5 (2006), 835–843  mathnet  crossref  mathscinet  zmath
    9. Calvert W., Knight J.F., “Classification from a computable viewpoint”, Bulletin of Symbolic Logic, 12:2 (2006), 191–218  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    11. E. B. Fokina, “Index sets of decidable models”, Siberian Math. J., 48:5 (2007), 939–948  mathnet  crossref  mathscinet  zmath  isi
    12. Khoussainov B., Nies A., Rubin S., Stephan F., “Automatic Structures: Richness and Limitations”, Logical Methods in Computer Science, 3:2 (2007), 2  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  adsnasa  isi
    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  crossref  mathscinet  zmath  isi  scopus
    16. E. N. Pavlovskii, “Estimation of the algorithmic complexity of classes of computable models”, Siberian Math. J., 49:3 (2008), 512–523  mathnet  crossref  mathscinet  zmath  isi
    17. Downey R., Montalban A., “The isomorphism problem for torsion-free Abelian groups is analytic complete”, Journal of Algebra, 320:6 (2008), 2291–2300  crossref  mathscinet  zmath  isi  scopus
    18. Rubin S., “Automata presenting structures: A survey of the finite string case”, Bulletin of Symbolic Logic, 14:2 (2008), 169–209  crossref  mathscinet  zmath  isi  scopus
    19. Greenberg N., Montalban A., “Ranked structures and arithmetic transfinite recursion”, Transactions of the American Mathematical Society, 360:3 (2008), 1265–1307  crossref  mathscinet  zmath  isi  scopus
    20. E. N. Pavlovskii, “Indeksnye mnozhestva prostykh modelei”, Sib. elektron. matem. izv., 5 (2008), 200–210  mathnet  mathscinet
    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  crossref  mathscinet  zmath  isi  scopus
    22. E. N. Pavlovskii, “Slozhnost indeksnykh mnozhestv nekotorykh klassov modelei”, Vestn. NGU. Ser. matem., mekh., inform., 8:1 (2008), 71–76  mathnet
    23. E. B. Fokina, “Algoritmicheskie svoistva modelei signatury s dvumya odnomestnymi funktsionalnymi simvolami”, Vestn. NGU. Ser. matem., mekh., inform., 8:1 (2008), 90–101  mathnet
    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  mathnet
    25. Khoussainov B., Minnes M., “Model-theoretic complexity of automatic structures”, Annals of Pure and Applied Logic, 161:3 (2009), 416–426  crossref  mathscinet  zmath  isi  scopus
    26. Fokina E.B., “Index sets for some classes of structures”, Annals of Pure and Applied Logic, 157:2–3 (2009), 139–147  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  mathscinet  isi
    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  crossref  mathscinet  zmath  isi  scopus
    30. Melnikov A.G., “Computable Ordered Abelian Groups and Fields”, Programs, Proofs, Processes, Lecture Notes in Computer Science, 6158, 2010, 321–330  crossref  mathscinet  zmath  adsnasa  isi  scopus
    31. S. S. Goncharov, “Degrees of autostability relative to strong constructivizations”, Proc. Steklov Inst. Math., 274 (2011), 105–115  mathnet  crossref  mathscinet  isi  elib  elib
    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  mathnet  crossref  mathscinet  zmath  isi
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  elib  scopus
    35. N. T. Kogabaev, “The complexity of isomorphism problem for computable projective planes”, J. Math. Sci., 203:4 (2014), 509–515  mathnet  crossref
    36. Kuske D., Liu J., Lohrey M., “The Isomorphism Problem for Omega-Automatic Trees”, Ann. Pure Appl. Log., 164:1 (2013), 30–48  crossref  mathscinet  zmath  isi  scopus
    37. S. S. Goncharov, “Index Sets of Almost Prime Constructive Models”, J. Math. Sci., 205:3 (2015), 355–367  mathnet  crossref
    38. N. A. Bazhenov, “Computable numberings of the class of Boolean algebras with distinguished endomorphisms”, Algebra and Logic, 52:5 (2013), 355–366  mathnet  crossref  mathscinet  isi
    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  mathnet  crossref
    40. Montalban A., “Copyable Structures”, J. Symb. Log., 78:4 (2013), 1199–1217  crossref  mathscinet  zmath  isi  scopus
    41. Becker H., “Isomorphism of Computable Structures and Vaught's Conjecture”, J. Symb. Log., 78:4 (2013), 1328–1344  crossref  mathscinet  zmath  isi  scopus
    42. M. V. Dorzhieva, “Eliminatsiya metarekursii iz teoremy Ouinsa”, Vestn. NGU. Ser. matem., mekh., inform., 14:1 (2014), 35–43  mathnet
    43. Melnikov A.G., “Computable Abelian Groups”, Bull. Symb. Log., 20:3 (2014), 315–356  crossref  mathscinet  zmath  isi  elib  scopus
    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  mathscinet  isi
    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  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    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  mathnet  crossref  crossref  mathscinet  isi
    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  mathnet  crossref  crossref
    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  mathnet  crossref  crossref  mathscinet  isi
    49. Calvert W., “Pac Learning, Vc Dimension, and the Arithmetic Hierarchy”, Arch. Math. Log., 54:7-8 (2015), 871–883  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  elib  scopus
    52. N. A. Bazhenov, “Degrees of autostability relative to strong constructivizations for Boolean algebras”, Algebra and Logic, 55:2 (2016), 87–102  mathnet  crossref  crossref  isi
    53. N. A. Bazhenov, “Degrees of autostability for linear orderings and linearly ordered Abelian groups”, Algebra and Logic, 55:4 (2016), 257–273  mathnet  crossref  crossref  isi
    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  mathnet  crossref  crossref  isi
    55. Miller R. Ng K.M., “Finitary Reducibility on Equivalence Relations”, J. Symb. Log., 81:4 (2016), 1225–1254  crossref  mathscinet  zmath  isi  scopus
    56. Downey R.G., Melnikov A.G., Ng K.M., “A Friedberg Enumeration of Equivalence Structures”, J. Math. Log., 17:2 (2017), UNSP 1750008  crossref  mathscinet  isi  scopus
    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  mathnet  crossref  crossref  isi  elib  elib
    58. Melnikov A.G., “Torsion-Free Abelian Groups With Optimal Scott Families”, J. Math. Log., 18:1 (2018)  crossref  mathscinet  isi  scopus
    59. Knight J.F. Saraph V., “Scott Sentences For Certain Groups”, Arch. Math. Log., 57:3-4 (2018), 453–472  crossref  mathscinet  zmath  isi  scopus
    60. Melnikov A.G. Ng K.M., “Computable Torsion Abelian Groups”, Adv. Math., 325 (2018), 864–907  crossref  mathscinet  zmath  isi  scopus
    61. Lange K. Miller R. Steiner R.M., “Classifications of Computable Structures”, Notre Dame J. Form. Log., 59:1 (2018), 35–59  crossref  mathscinet  zmath  isi  scopus
    62. A. K. Voǐtov, “The $\Delta^0_\alpha$-computable enumerations of the classes of projective planes”, Siberian Math. J., 59:2 (2018), 252–263  mathnet  crossref  crossref  isi  elib
    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  mathnet  crossref  crossref  isi  elib
    64. Harrison-Trainor M., “There Is No Classification of the Decidably Presentable Structures”, J. Math. Log., 18:2 (2018), UNSP 1850010  crossref  mathscinet  isi  scopus
    65. M. V. Dorzhieva, “Odnoznachnaya numeratsiya dlya semeistva vsekh $\Sigma^{1}_{2}$-mnozhestv”, Sib. zhurn. chist. i prikl. matem., 18:2 (2018), 47–52  mathnet  crossref
    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  mathnet  crossref  crossref  isi
    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  mathnet  crossref  crossref  isi  elib
    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  crossref  mathscinet  zmath  isi  scopus
    69. Mahmoud M.A., “Degrees of Categoricity of Trees and the Isomorphism Problem”, Math. Log. Q., 65:3 (2019), 293–304  crossref  mathscinet  zmath  isi  scopus
    70. Downey R. Melnikov A. Ng K.M., “Categorical Linearly Ordered Structures”, Ann. Pure Appl. Log., 170:10 (2019), 1243–1255  crossref  mathscinet  zmath  isi  scopus
    71. Miller R., “Isomorphism and Classification For Countable Structures”, Computability, 8:2 (2019), 99–117  crossref  mathscinet  zmath  isi  scopus
    72. Quinn S.B., “Scott Sentences For Equivalence Structures”, Arch. Math. Log., 59:3-4 (2020), 453–460  crossref  mathscinet  zmath  isi  scopus
    73. M. I. Marchuk, “Indeksnoe mnozhestvo avtoustoichivykh uporyadochennykh abelevykh grupp”, Matem. tr., 23:1 (2020), 169–176  mathnet  crossref
    74. N. Bazhenov, M. Marchuk, “A note on decidable categoricity and index sets”, Sib. elektron. matem. izv., 17 (2020), 1013–1026  mathnet  crossref
    75. Harrison-Trainor M., Melnikov A., Ng K.M., “Computability of Polish Spaces Up to Homeomorphism”, J. Symb. Log., 85:4 (2020), 1664–1686  crossref  mathscinet  zmath  isi  scopus
    76. Bazhenov N. Fokina E. San Mauro L., “Learning Families of Algebraic Structures From Informant”, Inf. Comput., 275 (2020), 104590  crossref  mathscinet  zmath  isi  scopus
    77. Downey R., Melnikov A., Ng K.M., “Enumerating Abelian P-Groups”, J. Algebra, 560 (2020), 745–790  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    80. Bazhenov N. Goncharov S. Melnikov A., “Decompositions of Decidable Abelian Groups”, Int. J. Algebr. Comput., 30:1 (2020), 49–90  crossref  mathscinet  zmath  isi  scopus
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:646
    Full text:222
    First page:1

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021