Show that it is undecidable, given the source code of a program Q, to tell whether or not any of the following is true: (i) Q halts on input 0. (ii) Q is total – that is, Q(y) halts for all y. (iii) Q(y) = true for all y. (iv) The set of y on which Q halts is finite. (v) There is a y such that Q(y) = y. (vi) Given a second program R, Q is equivalent to R. That is, even though Q and R have different source codes, they compute the same partial function – for all y, either Q(y) and R(y) both halt and return the same answer, or neither halts. Prove each of these by reducing Halting to them. That is, show to how convert an instance (P, x) of Halting to an instance of the problem above. For instance, you can modify P’s source code, or write a new program that calls P as a subroutine. Each of these is asking for a Turing reduction; your reduction does not necessarily have to map yes-instances to yes-instances and no-instances to no-instances – all that matters is that if you could solve the problem, then you could solve Halting
Show that it is undecidable, given the source code of a
not any of the following is true:
(i) Q halts on input 0.
(ii) Q is total – that is, Q(y) halts for all y.
(iii) Q(y) = true for all y.
(iv) The set of y on which Q halts is finite.
(v) There is a y such that Q(y) = y.
(vi) Given a second program R, Q is equivalent to R. That is, even though Q and R
have different source codes, they compute the same partial function – for all y,
either Q(y) and R(y) both halt and return the same answer, or neither halts.
Prove each of these by reducing Halting to them. That is, show to how convert an
instance (P, x) of Halting to an instance of the problem above. For instance, you can
modify P’s source code, or write a new program that calls P as a subroutine. Each
of these is asking for a Turing reduction; your reduction does not necessarily have to
map yes-instances to yes-instances and no-instances to no-instances – all that matters
is that if you could solve the problem, then you could solve Halting
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
