The Complexity Hierarchy The complexity hierarchy is a monument to our collective understanding of computation and its limitations. In fact, you may already be familiar with the classes P and NP from CS61B. In this problem, we will focus on decision problems like the Halting Problem, where the output is Yes (True) or No (False), and explore the classes RE, CORE, and R. (a) A problem is recursively enumerable (RE) if there exists a program P that can print out all the inputs for which the answer is Yes, and no inputs for which the answer is No. The program P can print out a given input multiple times, so long as every input gets printed eventually. The program P can run forever, so long as every input which should be printed is at a finite index in the printed output. Prove that the Halting Problem belongs in RE. Namely, prove that it is possible to write a program P which: • runs forever over all possible programs M and inputs x, and prints out strings to the console, • for every (M, x), if M(x) halts, then P eventually prints out (M, x), • for every (M, x), if M(x) does NOT halt, then P never prints out (M, x). CS 70, Summer 2020, ork In this context, P is called an enumerator. (Hint: Consider the tail of a dove.)
(b) An equivalent definition of RE is as follows: A problem belongs in RE if there exists a program P that will output Yes when given an input x for which the answer is Yes. If the answer is No, then P'(x) may output No or loop forever. As an optional exercise, you should be able to convince yourself that this is indeed an equivalent definition. Prove that the Halting Problem belongs in RE using this equivalent definition. Namely, prove that it is possible to write a program P' which: • takes as input a program M and input x. . if M halts on input x, then P' should print Yes. • if M does not halt on input x, then P' may output No or loop forever. In this context, P' is called a recognizer.
(c) As you might suspect, a problem is co-recursively enumerable (CORE) if its complement is in RE. The complement of a decision problem A is another problem A' where A'(x) is Yes iff A(X) is No, and A'(x) is No iff A(x) is Yes. State the complement of the Halting Problem.