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?
The Church/Turing thesis says that all algorithmic processes can be carried out on a Turing machine. Another way to say this is that a practical model of computing cannot have more power than a Turing machine. It can, however, have less power. (Finite state machines have less power than Turing machines.)
Does a computer with two stacks have the same, less or more power than a computer with one tape?
A computer with two stacks has the same power as a Turing machine. We saw that two stacks can used to simulate a single 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?
No. It is possible to tell that certain grammars are ambiguous, and that certain others are not ambiguous. It is just not possible to write a computer program that will tell you whether an arbitrary context-free grammar is ambiguous.
Is the set {p | p(p) terminates} computable?
No, it is not computable. This is the set K that we showed is uncomputable in class using diagonalization.
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.
No. This problem is not computable by Rice's theorem. The input to the problem is a program, written in C++. But C++ has the same power as a Turing machine, and any Turing machine program could be written in C++. Some C++ programs have the property that they print "yes" on an empty input, and some do not. So the set of all such programs is nontrivial. If two programs are equivalent, then either both print "yes" on an empty input, or both do not. So this problem respects equivalence.
Let A = {p | p(x) loops forever whenever the first letter of x is 'a'}. Is A computable? Justify your answer.
No, this is not computable by Rice's theorem. A is nontrivial because some programs loop forever on all inputs whose first letter is 'a', and some do not have that property. Suppose p and q are equivalent programs. If p is in A then p loops forever on all inputs that start with 'a'. But, since q is equivalent to p, q also loops forever on all inputs that start with 'a', and so q is in A. So A respects equivalence.
Let B = {p | p is a program whose length is a prime number}. Is B a computable language?
Yes, B is a computable language. Just count how long a program is, and check whether the count is prime.
What is the definition of an m-reduction from A to B?
An m-reduction from A to B is a computable function f such that, for every x, x is in A if and only if f(x) is in 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.
It is possible to write a program R(p) that produces the following program Tp as its answer.
Tp(y)
----
Run p(0) and give the same answer that it gives.
Notice that program Tp ignores its own input y, and
instead runs program p on input 0. So, regardless of what
y is, Tp(y)
does exactly the same thing as
p(0). In particular, choosing y = 1,
you can see that Tp(1) does the same thing
as p(0). So p terminates on input 0 if and only if
Tp terminates on input 1.
That is, p is in A if and only if
Tp is in B.
By the definition of a reduction, R is a reduction from A to B. R is certainly computable. Just write program Tp, substituting p where it is used. And, since R(p) = Tp, we have seen that p is in A if and only if R(p) is in B, for every p.