University of Sussex Spring 2021 Informatics
Limits of Computation
Exercises 5
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 accord- ingly)? Explain your answer. In cases where problems are decid- able, sketch the decision procedure. Hint: Use Rice’s Theorem to explain undecidability where appropriate.
(a) A is the set of WHILE-programs p such that p terminates for all inputs. In other words:
WHILE
A = {p |∀d ∈ D. p (d)↓}
(b) A is the set of WHILE-programs p such that p is one of two
programs, in other words:
p=readX{while1{}}writeX ∨
A= p | p=readZ{Z:=consXnil}writeZ
(c) A is the set of WHILE-programs p that decide whether its
argument d is nil. In other words: WHILE
A={p| ∀d∈D.p (d)=trueiffd=nil} Any WHILE-program p can be regarded as element of D via our
encoding, given in Lecture 6, p. 2. Give each one example of
(a) an undecidable problem that is semi-decidable
1
(b) a decidable problem that is semi-decidable
(c) an undecidable problem that is not semi-decidable.
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 Lec- ture 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.
(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.
2