I need help with problem 34 i)
Here Section 1.3 refers to the Halting problem shown below,
34. i. In Section 1.3 we showed that He is undecidable, that is there is no program that for all can output TRUE if program Phalts on input x and outputs FALSE if program P, does not halt on input z. Now show that H(x, 2.r) is undecidable, i.e. show there is no program that for all u can output TRUE if program Phalts on input 2x and outputs False if program P. does not halt on input 2.r. Hint: You will want to build a program E (analogous to D for the solution shown in Sec- tion 1.3), but what matters particularly is the action of E on even valued inputs. In particular, this type of difficulty occurs with the Halting Problem, which seeks to answer the following class of questions: Does the computation of program PO on input o eventually terminate where x is a possible input for P? Note that P not terminating on input might be the result of an infinite loop or an unbounded recursion. To prove our result, let us assume, in order to obtain a contradiction, that there is a 2-input program H that solves the halting problem. H computes the table shown in Figure 5.2. The ith row describes the behavior of the i-th program, P. on each of its possible inputs, w1, W2, ... . Remember that we use an integer to represent the corresponding string, so rather than write HP, wy), we will write Hry) for short. Using H as a subroutine we are going to construct a function D WW2 ... Wp (computed by program Pa in the ta- > input ble) which has the opposite behavior PYNY... to what is shown in the correspond- P2 NNN ... ing diagonal entry in the table. That is, if H C) = "Yes", then Y = terminating D(2) = Pac) runs forever, while if N = runs forever H(2, ) = "No" then D(2) eventu- ally terminates with output "Yes" PANY ... ? (the particular output is unimpor- program tant; what matters is that it halts). D is defined as follows. Figure 1.8: Function D. Key: D(2) Simulate H2, 0); If H(2, ) outputs "Yes" then loop forever else (* H(2,7) outputs "No" and *) D(x) outputs "Yes" Side note: If c is not a valid program, we define H2,y) = "Yes." Observe that D(2) terminates H1,I) outputs "No" => 0(x) does not terminate. Setting r=D yields D(D) terminates D(D) does not terminate, which is the contradiction we seek. This contradiction shows that the assumption that H exists must be false. Comments. i. We have actually shown that there is no program H that can answer the question of "does program P on input P eventually halt?" for all possible programs P. Notice that the difficulties occurred when considering the self-referential D(D). ii. One way of viewing this result is that it states that there is no algorithm to debug programs in general (by in general we mean that it works for every possible program). For if we cannot even determine in general if a program eventually stops on a given arbitrary input, how could we determine whether a program performs the computation that we want it to perform. 34. i. In Section 1.3 we showed that He is undecidable, that is there is no program that for all can output TRUE if program Phalts on input x and outputs FALSE if program P, does not halt on input z. Now show that H(x, 2.r) is undecidable, i.e. show there is no program that for all u can output TRUE if program Phalts on input 2x and outputs False if program P. does not halt on input 2.r. Hint: You will want to build a program E (analogous to D for the solution shown in Sec- tion 1.3), but what matters particularly is the action of E on even valued inputs. In particular, this type of difficulty occurs with the Halting Problem, which seeks to answer the following class of questions: Does the computation of program PO on input o eventually terminate where x is a possible input for P? Note that P not terminating on input might be the result of an infinite loop or an unbounded recursion. To prove our result, let us assume, in order to obtain a contradiction, that there is a 2-input program H that solves the halting problem. H computes the table shown in Figure 5.2. The ith row describes the behavior of the i-th program, P. on each of its possible inputs, w1, W2, ... . Remember that we use an integer to represent the corresponding string, so rather than write HP, wy), we will write Hry) for short. Using H as a subroutine we are going to construct a function D WW2 ... Wp (computed by program Pa in the ta- > input ble) which has the opposite behavior PYNY... to what is shown in the correspond- P2 NNN ... ing diagonal entry in the table. That is, if H C) = "Yes", then Y = terminating D(2) = Pac) runs forever, while if N = runs forever H(2, ) = "No" then D(2) eventu- ally terminates with output "Yes" PANY ... ? (the particular output is unimpor- program tant; what matters is that it halts). D is defined as follows. Figure 1.8: Function D. Key: D(2) Simulate H2, 0); If H(2, ) outputs "Yes" then loop forever else (* H(2,7) outputs "No" and *) D(x) outputs "Yes" Side note: If c is not a valid program, we define H2,y) = "Yes." Observe that D(2) terminates H1,I) outputs "No" => 0(x) does not terminate. Setting r=D yields D(D) terminates D(D) does not terminate, which is the contradiction we seek. This contradiction shows that the assumption that H exists must be false. Comments. i. We have actually shown that there is no program H that can answer the question of "does program P on input P eventually halt?" for all possible programs P. Notice that the difficulties occurred when considering the self-referential D(D). ii. One way of viewing this result is that it states that there is no algorithm to debug programs in general (by in general we mean that it works for every possible program). For if we cannot even determine in general if a program eventually stops on a given arbitrary input, how could we determine whether a program performs the computation that we want it to perform
