Thursday, June 20, 2019 10:00 am

10:00 am
EDT (GMT 04:00)
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 coc.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