You should be aware of definitions. The following are problems that need to be worked out.
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?
Let C = {p | p is a Java program that contains exactly one static variable of type int called frog, and, when the program is run on an empty input, at some point it stored value 1 into frog.
Define A = {(p,q) | p and q are programs, p(0) halts and q(1) loops forever}, and define B = {p | p(0) halts}. Give an m-reduction from B to A.
Define A = {p | p is a program where p(3) halts}, and define B = {p | p is a program where p(10) halts}. Give an m-reduction from A to B.
Suppose A and B are two computable languages over alphabet {a,b,c,d}. Is the intersection of A and B necessarily computable? Explain. (The intersection of A and B is the set of all strings that are both in A and in B.)
Suppose A and B are two uncomputable languages over alphabet {a,b,c,d}. Is the intersection of A and B necessarily uncomputable? Explain.