In computability theory, a subset of the natural numbers is called simple if it is computably enumerable (c.e.) and co-infinite (i.e. its complement is infinite), but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not computable.
YouTube Encyclopedic
-
1/3Views:65 3064 135702
-
How to build a set in one day
-
Simple Set Pool Setup (English)
-
SIMPLE Set & Forget PIN BAR Forex Swing Trading Entry 2017 | NZD/CAD 9 MONTHS LONG
Transcription
Relation to Post's problem
Simple sets were devised by Emil Leon Post in the search for a non-Turing-complete c.e. set. Whether such sets exist is known as Post's problem. Post had to prove two things in order to obtain his result: that the simple set A is not computable, and that the K, the halting problem, does not Turing-reduce to A. He succeeded in the first part (which is obvious by definition), but for the other part, he managed only to prove a many-one reduction.
Post's idea was validated by Friedberg and Muchnik in the 1950s using a novel technique called the priority method. They give a construction for a set that is simple (and thus non-computable), but fails to compute the halting problem.[1]
Formal definitions and some properties
In what follows, denotes a standard uniformly c.e. listing of all the c.e. sets.
- A set is called immune if is infinite, but for every index , we have . Or equivalently: there is no infinite subset of that is c.e..
- A set is called simple if it is c.e. and its complement is immune.
- A set is called effectively immune if is infinite, but there exists a recursive function such that for every index , we have that .
- A set is called effectively simple if it is c.e. and its complement is effectively immune. Every effectively simple set is simple and Turing-complete.
- A set is called hyperimmune if is infinite, but is not computably dominated, where is the list of members of in order.[2]
- A set is called hypersimple if it is simple and its complement is hyperimmune.[3]
Notes
References
- Soare, Robert I. (1987). Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. ISBN 3-540-15299-7. Zbl 0667.03030.
- Odifreddi, Piergiorgio (1988). Classical recursion theory. The theory of functions and sets of natural numbers. Studies in Logic and the Foundations of Mathematics. Vol. 125. Amsterdam: North Holland. ISBN 0-444-87295-7. Zbl 0661.03029.
- Nies, André (2009). Computability and randomness. Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034.