Editing Computably enumerable set (section)

==Equivalent formulations==
The following are all equivalent properties of a set ''S'' of natural numbers:

;Semidecidability<nowiki>:</nowiki>
:*The set ''S'' is computably enumerable. That is, ''S'' is the domain (co-range) of a partial computable function.
:*The set ''S'' is <math>\Sigma^0_1</math> (referring to the [[arithmetical hierarchy]]).<ref>{{cite book |last1=Downey |first1=Rodney G. |last2=Hirschfeldt |first2=Denis R. |title=Algorithmic Randomness and Complexity |date=29 October 2010 |publisher=Springer Science & Business Media |isbn=978-0-387-68441-3 |page=23 |url=https://books.google.com/books?id=FwIKhn4RYzYC&pg=PA23 |language=en}}</ref>
:*There is a partial computable function ''f'' such that: <math display="block"> f(x) =
\begin{cases} 
1 &\mbox{if}\ x \in S \\
\mbox{undefined/does not halt}\ &\mbox{if}\ x \notin S
\end{cases}
</math>
;Enumerability<nowiki>:</nowiki>
:*The set ''S'' is the range of a partial computable function.
:*The set ''S'' is the range of a total computable function, or empty. If ''S'' is infinite, the function can be chosen to be [[injective]].
:*The set ''S'' is the range of a [[primitive recursive function]] or empty. Even if ''S'' is infinite, repetition of values may be necessary in this case.
;Diophantine<nowiki>:</nowiki>
:*There is a polynomial ''p'' with integer coefficients and variables ''x'', ''a'', ''b'', ''c'', ''d'', ''e'', ''f'', ''g'', ''h'', ''i'' ranging over the natural numbers such that <math display="block">x \in S \Leftrightarrow \exists a,b,c,d,e,f,g,h,i \ ( p(x,a,b,c,d,e,f,g,h,i) = 0).</math> (The number of bound variables in this definition is the best known so far; it might be that a lower number can be used to define all Diophantine sets.)
:*There is a polynomial from the integers to the integers such that the set ''S'' contains exactly the non-negative numbers in its range.

The equivalence of semidecidability and enumerability can be obtained by the technique of [[Dovetailing (computer science)|dovetailing]].

The Diophantine characterizations of a computably enumerable set, while not as straightforward or intuitive as the first definitions, were found by [[Yuri Matiyasevich]] as part of the negative solution to [[Hilbert's tenth problem|Hilbert's Tenth Problem]]. Diophantine sets predate recursion theory and are therefore historically the first way to describe these sets (although this equivalence was only remarked more than three decades after the introduction of computably enumerable sets).

{| style="float:right"
| [[File:Recursive enumeration of all halting Turing machines.gif|thumb|450px|A computable enumeration of the set of all Turing machines halting on a fixed input: Simulate all Turing machines (enumerated on vertical axis) step by step (horizontal axis), using the shown diagonalization scheduling. If a machine terminates, print its number. This way, the number of each terminating machine is eventually printed. In the example, the algorithm prints "9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ..."]]
|}