Logic Seminar

Time: Friday, 9/26, 2:30-3:30pm


Speaker: Russell Miller, City University of New York

http://qcpages.qc.cuny.edu/~rmiller/

Title: Effective classification of computable structures
Abstract: The paradigm of a computable classification was given by Friedberg, who produced a uniformly computable listing of all computably enumerable sets, with no set appearing more than once in the listing. That is, he gave a computable classification of the computably enumerable sets up to equality. We apply 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. We then give a 0'-computable classification of the computable equivalence structures. We conjecture that there is no computable classification of the computable equivalence structures.