Turing computable embeddings, computable infinitary equivalence, and linear orders. / Bazhenov, Nikolay.
Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings. ed. / J Kari; F Manea; Petre. Vol. 10307 LNCS Springer-Verlag GmbH and Co. KG, 2017. p. 141-151 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10307 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Turing computable embeddings, computable infinitary equivalence, and linear orders
AU - Bazhenov, Nikolay
N1 - Publisher Copyright: © Springer International Publishing AG 2017.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - We study Turing computable embeddings for various classes of linear orders. The concept of a Turing computable embedding (or tc-embedding for short) was developed by Calvert, Cummins, Knight, and Miller as an effective counterpart for Borel embeddings. We are focused on tc-embeddings for classes equipped with computable infinitary Σα equivalence, denoted by ∼c α. In this paper, we isolate a natural subclass of linear orders, denoted by WMB, such that (WMB, ≅) is not universal under tc-embeddings, but for any computable ordinal α ≥ 5, (WMB, ∼c α) is universal under tc-embeddings. Informally speaking, WMB is not tc-universal, but it becomes tc-universal if one imposes some natural restrictions on the effective complexity of the syntax. We also give a complete syntactic characterization for classes (K, ≅) that are Turing computably embeddable into some specific classes (C, ≅) of well-orders. This extends the similar result of Knight, Miller, and Vanden Boom for the class of all finite linear orders Cfin.
AB - We study Turing computable embeddings for various classes of linear orders. The concept of a Turing computable embedding (or tc-embedding for short) was developed by Calvert, Cummins, Knight, and Miller as an effective counterpart for Borel embeddings. We are focused on tc-embeddings for classes equipped with computable infinitary Σα equivalence, denoted by ∼c α. In this paper, we isolate a natural subclass of linear orders, denoted by WMB, such that (WMB, ≅) is not universal under tc-embeddings, but for any computable ordinal α ≥ 5, (WMB, ∼c α) is universal under tc-embeddings. Informally speaking, WMB is not tc-universal, but it becomes tc-universal if one imposes some natural restrictions on the effective complexity of the syntax. We also give a complete syntactic characterization for classes (K, ≅) that are Turing computably embeddable into some specific classes (C, ≅) of well-orders. This extends the similar result of Knight, Miller, and Vanden Boom for the class of all finite linear orders Cfin.
KW - Computable infinitary equivalence
KW - Computable structure
KW - Linear order
KW - Ordinal
KW - Turing computable embedding
KW - ALGEBRAIC STRUCTURES
KW - RECURSIVE STRUCTURES
UR - http://www.scopus.com/inward/record.url?scp=85020849158&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-58741-7_15
DO - 10.1007/978-3-319-58741-7_15
M3 - Conference contribution
AN - SCOPUS:85020849158
SN - 9783319587400
VL - 10307 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 141
EP - 151
BT - Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings
A2 - Kari, J
A2 - Manea, F
A2 - Petre, null
PB - Springer-Verlag GmbH and Co. KG
T2 - 13th Conference on Computability in Europe, CiE 2017
Y2 - 12 June 2017 through 16 June 2017
ER -
ID: 10184739