Computability Seminar MSRI program on DDC-Effective coding and decoding in classes of structures

Organizer: V. Harizanov

For link contact harizanv@gwu.edu

Thursday, September 24, 12:00-1:00 on Zoom

Speaker:  Alexandra Soskova Sofia University, Bulgaria

Title: Effective coding and decoding in classes of structures

Abstract: 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) into 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.