CSCI 4602
Fall 2000
Practice questions for quiz 3.
- 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?
- 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 accepts input 0} and B = {p | p accepts input 1}.
Show that A m-reduces to B.
- Show that the language A = {p | p accepts input 0}
is recursively enumerable.