What is the definition of a Turing recognizable set?
What is the definition of an m-complete set?
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 A = {p | p accepts input 0} and B = {p | p accepts input 1}. Show that A m-reduces to B.
Show that the language A of the preceding problem is recursively enumerable.
Show that the language A = {p | p is a program and p(0) = 1} is m-complete.