Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets

We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elemen...

Full description

Saved in:
Bibliographic Details
Published in:The bulletin of symbolic logic 1996-06, Vol.2 (2), p.199-213
Main Authors: Harrington, Leo, Soare, Robert I.
Format: Article
Language:English
Subjects:
Automorphisms
Communications
Computability
Definability
Information content
Mathematical functions
Mathematical logic
Mathematical sets
Recursion theory
Recursively enumerable sets
Terminology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).
ISSN:1079-8986
1943-5894
DOI:10.2307/421110