Coding in graphs and linear orderings

Julia Knight, Alexandra Soskova, Stefan Vatev

There is a Turing computable embedding $\Phi$ of directed graphs $A$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform interpretation; i.e., for a…