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
27
28
29
30
31
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
  1. 2019 (177)
    1. November (11)
    2. October (19)
    3. September (13)
    4. August (7)
    5. July (12)
    6. June (18)
    7. May (22)
    8. April (11)
    9. March (25)
    10. February (17)
    11. January (22)
  2. 2018 (219)
    1. December (2)
    2. November (32)
    3. October (27)
    4. September (26)
    5. August (4)
    6. July (9)
    7. June (13)
    8. May (17)
    9. April (13)
    10. March (28)
    11. February (27)
    12. January (21)
  3. 2017 (281)
  4. 2016 (335)
  5. 2015 (209)
  6. 2014 (235)
  7. 2013 (251)
  8. 2012 (135)