Computability Learning Seminar

Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo

"The Isomorphism Problem of the Class of Computable Trees of Finite Rank"

We discussed before the isomorphism problem of the class $K_n$ of computable trees of rank $n$ for every natural number $n$, which we showed to be $\Pi_{2n}-$complete. Now we are looking at the class $K_{<\omega}$ of all computable trees of finite rank. We could show that the isomorphism problem of that class is complete with respect to the class of sets of the form $\bigcup_{n\in\omega}A_n$ where $A_i\subseteq A_{i+1}$, $A_i$ is $\Sigma^0_i$, and there exists a sequence of co-c.e.\ sets $\{C_m\}_{m\in\omega}$ such that $C_i\subseteq C_{i+1}$ and $C_i\cap A_m=A_i$ for all $i\leq m$.

MC 5479