University of Sussex Spring 2021 Informatics
Limits of Computation
Feedback for Exercises 5 Dr Bernhard Reus
WHILE-(Un)Decidability, Rice’s Theorem and Reduction (Lectures 8–10)
1. Below you find a list (a–c) of decision problems about (encod- ings of) WHILE-programs. Which of these problems are WHILE- decidable and which are undecidable? In other words, for which problems A can we write a WHILE-program that takes d ∈ D as input and decides d ∈ A? (returning true or false ac- cordingly)? Explain your answer. In cases where problems are decidable, sketch the decision procedure. Hint: Use Rice’s Theorem to explain undecidability where appropriate.
Answer:
(a) A is the set of WHILE-programs p, encoded i.e. in form p,
such that p terminates for all inputs.
Furthermore, we notice that the property we are consider- ing here is extensional, which means that the property of p only depends on the input-output behaviour of the pro- gram p rather than its appearance. This can be seen by writing down this problem (in this case property of WHILE- programs) more carefully: Program p terminates for all inputs is the following property (or set) A:
WHILE
We notice immediately that the property of programs in A WHILE
(i.e. p (d) ↓ for all d) is non-trivial, that is, we know that there is at least one program with this property, for in- stance program read X { } write X. Moreover, we know that not all programs in D terminate for all input. For in- stance, program read X { while X { } } write X does not terminate for any other input than nil.
Soifp Diffq
=q
(d)↓ foralld∈Dandthusp∈Aiffq∈A.
p∈Aif, andonlyif, p (d)↓ foralld∈D
WHILE
WHILE WHILE
wegetthatp (d)↓ foralld∈ 1
WHILE
As property A is about programs, non-trivial and exten- sional if satisfies all conditions of Rice’s theorem are there- fore we can reason by Rice’s theorem that A is undecidable.
(b) A is the set of WHILE-programs p where p is one of two programs, in other words:
p=readX{while1{}}writeX ∨ A= p | p=readZ{Z:=consXnil}writeZ
In this case A is the two-element set containing the (encod- ings of) the two programs above. We can write a program which inspects each node of an input program-as-data and returns false the moment it fails to find a match for the current node in one of the two elements of A. If each node is matched against each node of one or the other of the programs in A then our deciding program will return true. We notice that both programs in A are finite in length therefore our program always terminates. Since we are satisfying both conditions for the decidability of A we can state that this problem is decidable. Note that the encoded program use numbers top identify variables not names. Note: We assume that the numbering is uniquely determined, for instance by starting with 0 and numbering variable sin the order of appearance.
(c) A is the set of WHILE-programs p that decide whether its argument d is nil.
This property A of programs is clearly non-trivial, as we can think immediately of a program that can tell whether its input is nil, e.g.
read X{ if X {
Y:= false }
else {
Y:= true }
} write Y
and not all programs satisfy this property (pick your favourite different program :-)).
Secondly, this property A is extensional since it depends solely on the input-output behaviour of the program. This can be seen by writing up the definition of A formally again
2
and checking (as done for (a)). p∈Aif, andonlyif,
WHILE
WHILE
2. Give each one example of
(a) an undecidable problem that is semi-decidable: Answer: Halting Problem
(b) a decidable problem that is semi-decidable:
Answer: any decidable problem is semi-decidable, e.g. is a number even?
(c) an undecidable problem that is not semi-decidable: Answer: complement of the Halting problem.
3. Prove that for two sets (or problems) A and B, if A ≤rec B and B is decidable, then A is also decidable (as stated in Lecture 9), using “WHILE-decidable” as notion of “decidable”, i.e. WHILE- programs as effective procedures.
Proceed as follows:
(a) explain what A ≤rec B means. Answer:
A ≤rec B means that there is a total and (WHILE-)computable
function f : D → D such that x ∈ A if, and only if,
f(x) ∈ B.
Since f is (WHILE-)computable we therefore know there
p
(d) = true iff d = nil for all d ∈ D
WHILE WHILE
So if p
iffd=nilforalld∈Diff q (d)=trueiffd= nil for all d ∈ D iff q ∈ A.
Since all conditions of Rice’s theorem are met, it can be applied and Rice’s theorem tells us again that this problem is undecidable.
= q we get that p WHILE
(d) = true
must be a (WHILE-)program r that always terminates such WHILE
that r (d) = f(d) for all d ∈ D.
Note that we can replace WHILE here with any other rea- sonable notion of effective procedures.
(b) using the obtained assumption and the one obtained from the WHILE-decidability of B, write the program p that proves that A is WHILE-decidable.
Answer:
3
Our further assumption now is that B is decidable, which means that there is a WHILE-program q that aways termi-
WHILE
We need to prove that A is WHILE-decidable, that means
nates and for which we know that q (d) = true if,
and only if, d ∈ B for all d ∈ D.
we need to find a WHILE-program p that always terminates WHILE
and for which we know that p (d) = true if, and only if, d ∈ A for all d ∈ D.
How do we know how to program this? Well, the reduction givesustherecipe: x∈Aif,andonlyif,f(x)∈B. So to decide membership in A we “simply” need to program a procedure that checks whether f(x) is in B. The latter can be done with the help of the decision procedure for B and the implementation of f:
The required decision procedure p can thus be defined as follows:
p read d {
y :=
out := y
}
write out
By definition of p and using the semantics of WHILE-programs, we get (omitting the detailed steps of the semantics as done once on Exercise Sheet 2) that
(r
which by our assumption about q is true if, and only if, f(d) ∈ B. But because of our assumption that x ∈ A if, and only if, f(x) ∈ B, we get that
and so we have shown that p
It remains to show that p will always terminate, but this
is trivial, since we know that r and q always terminate by assumption.
We thus have proved that A is WHILE-decidable.
4
WHILE WHILE
WHILE WHILE
p (d) = q
(d)) = p (f(d))
WHILE WHILE
p (d) = q (f (d)) = true iff f (d) ∈ B iff d ∈ A
WHILE
(d) = true iffd ∈ A.