Degrees of Categorictiy of Trees of finite rank
Speaker:
Mohammad Mahmoud, University of Waterloo
Date and Time:
Friday, June 8, 2018 - 11:30am to 11:50am
Location:
University of Waterloo - MC 5501
Abstract:
For any natural number n≥0, it is easy to see that any computable tree of rank n+1 is 0(2n)-categorical. We show that 0(2n) is the strong degree of categoricity for some computable tree of rank n+1. Our work also shows that the isomorphism problem for the class of trees of rank n, n≥1, is Π02n-complete. The isomorphism problem for the class of trees of finite rank turns out to be interesting.