CSCI 4602
Fall 2001
Practice questions for quiz 4.

  1. What is the definition of a Turing recognizable set?

  2. What is the definition of an m-complete set?

  3. 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.

  4. Let A = {p | p accepts input 0} and B = {p | p accepts input 1}. Show that A m-reduces to B.

  5. Show that the language A of the preceding problem is recursively enumerable.

  6. Show that the language A = {p | p is a program and p(0) = 1} is m-complete.