Logic Seminar

Mohammad Mahmoud, University of Waterloo

"On the Computable Categoricity of Trees of Finite Height"

Looking at trees as logical ordered structures (T,<), we can talk about computable such structures and about the complexity (hardness) of isomorphisms between them. The taller the tree, the more complex the isomorphisms  (between its computable copies) can be. The results we will discuss are, in a sense, about which is the smallest height tree we can use to be able to find two copies of that tree between which isomorphisms are of a given complexity. Our trees are around half the height of those trees used for the same purpose by Lempp, McCoy, Miller and Solomon.

MC 5403