Some definitions

Definition 3   A decision problem is a problem where the output is $1$ or 0.

Definition 4   The corresponding language is $\{I\mid\textrm{ output on }I\textrm{ is }1\}$.

Reduce one language to another.

Definition 5   A many to one reduction from Language $L$ to language $M$, that is $L \leq M$, has the following form:

We have program for $L$, read $X$, return Program_For_$M$.

Go back to Hilbert's 10th problem: find an algorithm to determine if a polynomial has integer solution.

Theorem 6   There is no algorithm for determining if a polynomial has integer solutions.

Proof.

$$\mathrm{HALT}\leq \mathrm{HILBERT's 10th Problem}$$

Finally shown in 1970 by Matiyasevich. The detail of this proof is not mentioned in the class. People were trying to reach the final solution gradually, paper after paper. It took 70 years to finally get a function $f$ to transform $\mathrm{HALT}$'s input into $\mathrm{HILBERT's 10th Problem}$'s input, so we can see that, normally, to discover $f$ is the most tricky part of all these reductions. $\qedsymbol$