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?
Does a computer with two stacks have the same, less or more power than a computer with one tape?
The set of ambiguous context-free grammars is uncomputable. Does this mean that, given any given grammar, it is impossible to tell whether it is ambiguous?
Is the set {p | p(p) terminates} computable?
Consider restricted C++ 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 C++ 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) loops forever 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?
What is the definition of an m-reduction from A to B?
Let A = {p|p(0) terminates} and let B = {p | p(1) terminates}. Show that there is an m-reduction from A to B.