Editing Computability theory (section)

===Rice's theorem and the arithmetical hierarchy===
[[Henry Gordon Rice|Rice]] showed that for every nontrivial class ''C'' (which contains some but not all c.e. sets) the index set ''E'' = {''e'': the ''e''th c.e. set ''W<sub>e</sub>'' is in ''C''} has the property that either the [[halting problem]] or its complement is many-one reducible to ''E'', that is, can be mapped using a [[many-one reduction]] to ''E'' (see [[Rice's theorem]] for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the [[arithmetical hierarchy]]. For example, the index set FIN of the class of all finite sets is on the level Σ<sub>2</sub>, the index set REC of the class of all recursive sets is on the level Σ<sub>3</sub>, the index set COFIN of all cofinite sets is also on the level Σ<sub>3</sub> and the index set COMP of the class of all Turing-complete sets Σ<sub>4</sub>. These hierarchy levels are defined inductively, Σ<sub>''n''+1</sub> contains just all sets which are computably enumerable relative to Σ<sub>''n''</sub>; Σ<sub>1</sub> contains the computably enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.