In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
, a subset of the natural numbers is called simple if it is
computably enumerable
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
(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
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
.
Relation to Post's problem
Simple sets were devised by
Emil Leon Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Govern ...
in the search for a non-Turing-complete c.e. set. Whether such sets exist is known as
Post's problem
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
Overview
The concept of Turing degree is fund ...
. 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
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
, 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
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...
.
Post's idea was validated by Friedberg and Muchnik in the 1950s using a novel technique called the
priority method
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
Overview
The concept of Turing degree is fund ...
. They give a construction for a set that is simple (and thus non-computable), but fails to compute the halting problem.
[Nies (2009) p.35]
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.
[Nies (2009) p.27]
*A set
is called hypersimple if it is simple and its complement is hyperimmune.
[Nies (2009) p.37]
Notes
References
*
*
* {{cite book , last=Nies , first=André , title=Computability and randomness , series=Oxford Logic Guides , volume=51 , location=Oxford , publisher=Oxford University Press , year=2009 , isbn=978-0-19-923076-1 , zbl=1169.03034
Computability theory