Answer links should work now.
Briefly explain what the Church/Turing thesis says. Does it say that all models of computing have the same power? Is it possible to design and implement a language that offers less power than a Turing machine? More power?
Is a Turing machine with 2 tapes more powerful than a Turing machine with 1 tape. That is, does having 2 tapes allow you to recognize a language that you could not recognize with one tape?
The set of ambiguous context-free grammars is known to be uncomputable. Does this mean that, given a context-free grammar G, it is impossible to tell whether it is ambiguous, regardless of what G is?
Is the set {p | ∃x(p(x)↓)} computable? Why or why not?
Consider restricted Java programs that are only allowed to print "yes" or "no", and must terminate immediately after printing their answer. Is it possible to write a program that reads the text of such a Java program p and tells whether or not p will print "yes" when run on an empty input? Justify your answer.
Let A = {p | p(x)↑ whenever the first letter of x is 'a'}. Is A computable? Justify your answer.
Let B = {p | p is a program whose length is a prime number}. Is B a computable language? Justify your answer.
Does there exist a partially computable language that is not computable?
Does there exist a computable language that is not partially computable?
Does there exist an enumerable language that is not computable?
Does there exist an enumerable language that is not partially computable?