University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Computability Learning SeminarExport this event to calendar

Thursday, June 20, 2019 — 10:00 AM EDT

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

S M T W T F S
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2021 (35)
    1. May (1)
    2. April (4)
    3. March (11)
    4. February (9)
    5. January (10)
  2. 2020 (103)
    1. December (10)
    2. November (12)
    3. October (4)
    4. September (3)
    5. August (1)
    6. July (5)
    7. June (1)
    8. May (3)
    9. March (16)
    10. February (26)
    11. January (22)
  3. 2019 (199)
  4. 2018 (212)
  5. 2017 (281)
  6. 2016 (335)
  7. 2015 (211)
  8. 2014 (235)
  9. 2013 (251)
  10. 2012 (135)