CSCI 4602
Fall 2000
Practice questions for quiz 3.

  1. 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?

  2. Does a computer with two stacks have the same, less or more power than a computer with one tape?

  3. 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.

  4. Let A = {p | p accepts input 0} and B = {p | p accepts input 1}. Show that A m-reduces to B.

  5. Show that the language A = {p | p accepts input 0} is recursively enumerable.