CS计算机代考程序代写 University of Sussex Spring 2021 Informatics

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.
Soif􏰖p􏰗 Diff􏰖q􏰗
=􏰖q􏰗
(d)↓ foralld∈Dandthusp∈Aiffq∈A.
p∈Aif, andonlyif, 􏰖p􏰗 (d)↓ foralld∈D
WHILE
WHILE WHILE
wegetthat􏰖p􏰗 (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)=􏰯true􏰰iffd= 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 := d;
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.