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.

Logic SeminarExport this event to calendar

Thursday, June 4, 2015 — 2:00 PM EDT

Russell Miller, Queens College - City University of New York

"Effective Classification of Computable Structures”

Many classes of computable structures can be enumerated computably. For example, one readily gives a uniformly computable list of all computable linear orders, simply by enumerating the c.e. sub- sets of a single computable dense linear order. Of course, this list includes infinitely many computable copies of each computable linear order. To give a computable classification (up to isomorphism) of these linear orders would require computing such a list so that no two linear orders on the list are (classically) isomorphic to each other. This is known to be impossible.

The paradigm of a computable classification was given by Friedberg, who produced a uniformly computable listing of all c.e. sets, with no set appearing more than once in the listing. That is, he gave a computable classification of the c.e. sets up to equality. In joint work, Lange, Steiner, and the speaker have applied his method to yield a computable classification of the computable algebraic fields, up to (classical) isomorphism. We also follow Goncharov and Knight in showing that certain other classes have no computable classification.

Additionally, we give a 0’-computable classification of the computable equivalence structures. This result, which extends (and uses) more work of Goncharov and Knight, means that there is a uniformly 0’-computable listing of all computably presentable equivalence structures, with no isomorphisms be- tween any two distinct structures on the list; however, the structures on the list are only 0’-computable, not necessarily computable. We conjecture that there is no computable classification of the computable equivalence structures.

M3-4206

S M T W T F S
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
  1. 2021 (71)
    1. August (4)
    2. July (17)
    3. June (15)
    4. May (1)
    5. April (4)
    6. March (11)
    7. February (9)
    8. 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)