# Mathematical Sciences Research Institute

Home » DDC - Computability Theory: Effective coding and decoding in classes of structures

# Seminar

DDC - Computability Theory: Effective coding and decoding in classes of structures September 24, 2020 (09:00 AM PDT - 10:00 AM PDT)
Parent Program: Decidability, definability and computability in number theory: Part 1 - Virtual Semester MSRI: Online/Virtual
Speaker(s) Alexandra Soskova (Kliment Ohridski University of Sofia)
Description

Hilbert’s Tenth Problem was the only decision problem among his twenty-three problems. Precise mathematical theory of (in)computability and its interaction with number theory led to the negative solution of the problem. The seminar will focus on modern topics on computability-theoretic phenomena in number-theoretic and other algebraic and model-theoretic structures.

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

Video

#### Effective Coding And Decoding In Classes Of Structures

Abstract/Media

To participate in this seminar, please register here: https://www.msri.org/seminars/25206

There are several ways to code the information of one structure into another. Friedman and Stanley introduced Borel embeddings as a way of comparing classification problems for different classes of structures. A Borel embedding of a class K in a class K’ represents a uniform procedure for coding structures from K in structures from K’. Many Borel embeddings are actually Turing computable. When a structure A is coded in a structure B, effective decoding is represented by a Medvedev reduction of A to B. Harrison-Trainor, Melnikov, Miller, and Montalba’n defined a notion of an effective interpretation of A in B and proved that this is equivalent with the existence of a computable functor, i.e., a pair of Turing operators, one taking copies of B to copies of A, and the other taking isomorphisms between copies of B to isomorphisms between the corresponding copies of A. The first operator gives a Medvedev reduction.

The class of undirected graphs and the class of linear orderings both lie “on top” under Turing computable embeddings. The standard Turing computable embeddings of directed graphs (or structures for an arbitrary computable relational language) in undirected graphs come with uniform effective interpretations. We give examples of graphs that are not Medvedev reducible to any linear ordering, or to the jump of any linear ordering. Any graph can be interpreted in a linear ordering using computable Sigma_3 formulas. Friedman and Stanley gave a Turing computable embedding L of directed graphs in linear orderings. We show that there do not exist L_(omega_1,omega) formulas that uniformly interpret the input graph G in the output linear ordering L(G). This is joint work with J. Knight and S. Vatev.

 Notes 249 KB application/pdf

#### Effective Coding And Decoding In Classes Of Structures

 H.264 Video 25192_28690_8515_Effective_Coding_and_Decoding_in_Classes_of_Structures.mp4