Editing Arithmetical hierarchy (section)

== Relation to Turing machines ==
{{See also|Post's theorem}}

===Computable sets===
If ''S'' is a [[Computable function#Computable sets and relations|Turing computable set]], then both ''S'' and its [[Complement (set theory)|complement]] are recursively enumerable (if ''T'' is a Turing machine giving 1 for inputs in ''S'' and 0 otherwise, we may build a Turing machine halting only on the former, and another halting only on the latter).

By [[Post's theorem]], both ''S'' and its complement are in <math>\Sigma^0_1</math>. This means that ''S'' is both in <math>\Sigma^0_1</math> and in <math>\Pi^0_1</math>, and hence it is in <math>\Delta^0_1</math>.

Similarly, for every set ''S'' in <math>\Delta^0_1</math>, both ''S'' and its complement are in <math>\Sigma^0_1</math> and are therefore (by [[Post's theorem]]) recursively enumerable by some Turing machines ''T''<sub>1</sub> and ''T''<sub>2</sub>, respectively. For every number ''n'', exactly one of these halts. We may therefore construct a Turing machine ''T'' that alternates between ''T''<sub>1</sub> and ''T''<sub>2</sub>, halting and returning 1 when the former halts or halting and returning 0 when the latter halts. Thus ''T'' halts on every ''n'' and returns whether it is in ''S''; so ''S'' is computable.

===Summary of main results===
The Turing computable sets of natural numbers are exactly the sets at level <math>\Delta^0_1</math> of the arithmetical hierarchy.  The recursively enumerable sets are exactly the sets at level <math>\Sigma^0_1</math>.

No [[oracle machine]]  is capable of solving its own [[halting problem]] (a variation of Turing's proof applies).  The halting problem for a <math>\Delta^{0,Y}_n</math> oracle in fact sits in <math>\Sigma^{0,Y}_{n+1}</math>.

[[Post's theorem]] establishes a close connection between the arithmetical hierarchy of sets of natural numbers and the [[Turing degree]]s.  In particular, it establishes the following facts  for all ''n'' ≥ 1:
* The set <math>\emptyset^{(n)}</math> (the ''n''th [[Turing jump]] of the empty set) is [[Many-one reduction|many-one complete]] in <math>\Sigma^0_n</math>.
* The set <math>\mathbb{N} \setminus \emptyset^{(n)}</math> is many-one complete in <math>\Pi^0_n</math>.
* The set <math>\emptyset^{(n-1)}</math> is [[Turing complete set|Turing complete]] in <math>\Delta^0_n</math>.

The [[polynomial hierarchy]] is a "feasible resource-bounded" version of the arithmetical hierarchy in which polynomial length bounds are placed on the numbers involved (or, equivalently, polynomial time bounds are placed on the Turing machines involved).  It gives a finer classification of some sets of natural numbers that are at level <math>\Delta^0_1</math> of the arithmetical hierarchy.