The Halting Problem
Lecture Notes COMP 330 Winter 2021
Prakash Panangaden 10th March 2021
Suppose that we have a programming language in which we can manipulate strings, write while-loops, if-then-else statements, compose statements, for example with ; and do basic arithmetic. In this language, some of the programs halt on some of their inputs and on some other inputs they do not halt but run forever.
Note that the source code of a program is itself just a (long) string. We use the notation #P to mean the source code of the program P viewed as a string. Thus the source code of a program is just data that can be used by other programs. A compiler is just such a program; it gets the source code of a program as input and generates an executable version (which is just another string) as output. If P is a program and x is an input for the program we write P(x) for the effect of running P with input x. If C is a compiler then we can write C(#P) to mean, run C with with input the source code of P. There are lots of programs that take the source code of other programs as inputs and do something, perhaps answer some question about the property of the input program. A program could also take 2 inputs; if P is such a program and x and y are inputs to P, we can write P (x, y) for the effect of running P with inputs x and y.
Suppose we have a program H that takes two inputs. Suppose that this H can ¡°solve¡± the halting problem. If we give H input #P and x: H(#P,x) we get true if P(x) halts and false if P(x) loops forever. Now I can write a new program called S with the following source code:
Input : w
if H(w,w) then loop forever else halt.
It is easy to write something that loops forever (students in 202 are expert 1
at this). So everything in the above program S can easily be written in our language. Note that S expects only one input, it makes copies of that input.
Now consider S(#S). Does it halt or not? If we unpack this we get: if H(\#S,\#S) then loop forever else halt.
Now if S(#S) halts, the call to H will return true and we go to the then branch and loop!! If S(#S) loops forever, then the call to H returns false and we go to the else branch and halt! In either case we have a contradic- tion. Thus a program like H cannot exist.
2