 The essential technical achievement was that all semi-decidable (recursively enumerable) sets can be given a Diophantine representation, i.e., they can be represented by a simple formula of the form \(\exists x_1 \ldots \exists x_n (s = t)\), where \((s = t)\) is a Diophantine equation. More exactly, for any given recursively enumerable set \(S\), there is a Diophantine equation \((s(y, x_1 , \ldots ,x_n) = t(y, x_1 , \ldots ,x_n))\) such that \(\boldsymbol{n} \in S\) if and only if \(\exists x_1 \ldots \exists x_n (s(\underline{n}, x_1 , \ldots ,x_n) = t(\underline{n}, x_1 , \ldots ,x_n))\).