Turing computable embeddings, computable infinitary equivalence, and linear orders

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationUnveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings
EditorsJ Kari, F Manea, Petre
PublisherSpringer-Verlag GmbH and Co. KG
Pages141-151
Number of pages11
Volume10307 LNCS
ISBN (Print)9783319587400
DOIs
Publication statusPublished - 1 Jan 2017
Event13th Conference on Computability in Europe, CiE 2017 - Turku, Finland
Duration: 12 Jun 201716 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10307 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th Conference on Computability in Europe, CiE 2017
CountryFinland
CityTurku
Period12.06.201716.06.2017

Keywords

  • Computable infinitary equivalence
  • Computable structure
  • Linear order
  • Ordinal
  • Turing computable embedding
  • ALGEBRAIC STRUCTURES
  • RECURSIVE STRUCTURES

Fingerprint

Dive into the research topics of 'Turing computable embeddings, computable infinitary equivalence, and linear orders'. Together they form a unique fingerprint.

Cite this