Geodesic
Trees as a tool for modelling undecidable problems
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 1 (2023), pp. 5-23 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper proves undecidability and high undecidability (non-arithmeticity) of theories of trees (with various refinements of the concept of a tree and with various requirements for the properties of trees, including the finiteness of the number of vertices) in a language with a binary predicate letter corresponding to edges, equality, the transitive closure operator and congruence between pairs of vertices, which is defined as equality of the distance between the vertices of the first pair and the distance between the vertices of the second pair. It is shown that in many cases it is sufficient to apply the transitive closure operator only to the binary relation corresponding to edges, i.e., in fact, instead of the transitive closure operator, it is sufficient to consider the reachability relation; in some cases, we establish undecidability in a language without the transitive closure operator.
Keywords: first-order theory, trees, transitive trees, intransitive trees, transitive closure, undecidability, non-arithmeticity. 
@article{VTPMK_2023_1_a0,
     author = {M. N. Rybakov},
     title = {Trees as a tool for modelling undecidable problems},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {5--23},
     year = {2023},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2023_1_a0/}
}
TY  - JOUR
AU  - M. N. Rybakov
TI  - Trees as a tool for modelling undecidable problems
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2023
SP  - 5
EP  - 23
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2023_1_a0/
LA  - ru
ID  - VTPMK_2023_1_a0
ER  - 
%0 Journal Article
%A M. N. Rybakov
%T Trees as a tool for modelling undecidable problems
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2023
%P 5-23
%N 1
%U http://geodesic.mathdoc.fr/item/VTPMK_2023_1_a0/
%G ru
%F VTPMK_2023_1_a0
M. N. Rybakov. Trees as a tool for modelling undecidable problems. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 1 (2023), pp. 5-23. http://geodesic.mathdoc.fr/item/VTPMK_2023_1_a0/

[1] Berger R., “The undecidability of the domino problem”, Memoirs of the American Mathematical Society, 1966, no. 66 | DOI

[2] Boolos G. S., Burgess J. P., Jeffrey R. C., Computability and Logic, 5th edition, Cambridge University Press, New York, 2007, 364 pp.

[3] Church A., “A note on the Entscheidungsproblem”, Journal of Symbolic Logic, 1 (1936), 40–41

[4] Grädel E., Otto M., Rosen E., “Undecidability results on two-variable logics”, Archive for Mathematical Logic, 38 (1999), 313–354

[5] Harel D., “Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness”, Journal of the ACM, 33 (1986), 224–248

[6] Papadimitriou C. H., Computational Complexity, Addison–Wesley Publishing Company, 1995

[7] Rybakov M., “Computational complexity of theories of a binary predicate with a small number of variables”, Doklady Mathematics, 106:3 (2022), 458–461 | DOI

[8] Rybakov M., “Binary predicate, transitive closure, two or three variables: shall we play dominoes?”, Logical research, 2023 (in Russian)

[9] Rybakov M., Shkatov D., “Trakhtenbrot theorem for classical languages with three individual variables”, Proceedings of SAICSIT2019, v. 19, ACM, 2019

[10] Rybakov M., Shkatov D., “Algorithmic properties of first-order superintuitionistic logics of finite Kripke frames in restricted languages”, Journal of Logic and Computation, 31:2 (2021), 494–522

[11] Sipser M., Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012

[12] Surányi J., “Zur Reduktion des Entscheidungsproblems des logischen Funktioskalküls”, Mathematikai és Fizikai Lapok, 50 (1943), 51–74

[13] Tarski A., Givant S., A Formalization of Set Theory without Variables, American Mathematical Society, 1987

[14] Trakhtenbrot B. A., “The impossibility of an algorithm for the decidability problem on finite classes”, Proceedings of the USSR Academy of Sciences, 70:4 (1950), 569–572 (in Russian)

[15] Trakhtenbrot B. A., “On recursive separability”, Proceedings of the USSR Academy of Sciences, 88:6 (1953), 953–956 (in Russian)

[16] Turing A. M., “On computable numbers, with an application to the ‘Entscheidungsproblem’”, Proceedings of the London Mathematical Society, 42 (1936), 230–265