What is the definition of a Turing recognizable set?
A set S is Turing recognizable if there exists a Turing machine program p such that S = {x | p(x) halts}.
What is the definition of an m-complete set?
A set S is m-complete if S is Turing recognizable and for every Turing recognizable set X, X m-reduces to S.
The following is an incorrect argument that Hilbert's tenth problem is undecidable. What is wrong with the argument?
You could write a program to search for integer solutions to polynomial equations, but if there were no solution the program would run forever searching for a solution. Detecting whether the program runs forever requires solving the halting problem. But the halting problem is undecidable, so Hilbert's tenth problem is also undecidable.
Let HTP be Hilbert's tenth problem and H be the halting problem. The argument indicates that HTP could be solved if H could be solved. What the argument says is that HTP reduces to H. But combining that with the fact that H is undecidable tells you nothing. You would need instead to show that H reduces to HTP.
The argument suggests that this is the only possible way to solve HTP. But why can't there exist other approaches?
Let A = {p | p accepts input 0} and B = {p | p accepts input 1}. Show that A m-reduces to B.
For a given program p let f(p) be the program q written as follows.
q(x):
1. Run p(0).
2. If p(0) halts and accepts, then answer yes, else answer no.
Notice that q accepts in 1 if and only if p accepts 0. Since f
is clearly computable (it just has to write down program q, building
program p into it) f is an m-reduction from A to B.
Show that the language A of the preceding problem is recursively enumerable.
Write program R as follows.
R(p):
1. Run p(0).
2. If p halted and accepted input 0 then stop else loop forever.
Notice that R(p) halts if and only if p is in A. So A is
Turing recognizable. But that means A is recursively enumerable too,
since the terms Turing recognizable and recursively enumerable
have the same meaning.
Show that the language A = {p | p is a program and p(0) = 1} is m-complete.
We know that A is Turing-recognizable, by the argument of the preceding question. So it suffices to show that the halting problem m-reduces to A. Let f(p,x) produce program q, written as follows.
q(y):
1. Run p(x).
2. Answer 1.
Notice that q(0) answers 1 if and only if p(x) halts. (If p(x) does
not halt then q(0) gets stuck in step 1 and never gives an answer.)
So q is in A if and only if the pair (p,x) is in H. Since f is
clearly computable, it is an m-reduction from H to A.