Due. Wednesday, Feb. 9 at the beginning of class.
Write clearly readable and well thought out answers to all of the following questions.
Suppose that A and B are two computable languages over alphabet {a,b,c,d}. Is the intersection of A and B necessarily computable? Explain.
Suppose A and B are two uncomputable languages over alphabet {a,b,c,d}. Is the intersection of A and B necessarily uncomputable? Explain.
Let A = {p | p is a program so that p(1) and p(2) both halt, and p(1) gives the same answer as p(2)}. Is A a computable language? Why or why not?
Let R = {(p, q) | p(0) and q(0) both halt, and p(0) = q(0)}. Is R computable? Why or why not?
Let B = {p | p is a Java program that contains a static variable of type int called frog}. Is B computable? Why or why not?