When does a program halt?
Contents
When does a program halt?¶
\(\one\hash\) has programs which contain infinite loops such as
1###1####
This program never finishes. If you run this in an interpreter, you will need to figure out how to stop the execution. Most of the time, we are interested in programs which do finish. Actually, we are interested in programs which finish in a special way.
This last example had nothing to do with the words in the input registers before we ran the program. But usually the input registers make a difference to whether the program halts or not.
Definition
We (informally) say that a program \(p\) halts on some inputs if at some point during the execution of \(p\) on the inputs, the control transfers to right below the last instruction of \(p\). In more detail, suppose that \(p\) has n instructions. The formal definition is given below, after we discuss the remaining types of instructions.
In contrast, we say that p halts improperly if at some point during the execution of \(p\), the control tranfers either to a point before the beginning of \(p\) or to points more than one instruction beyond the last instruction of \(p\).
To see the difference, consider the following two programs: \(\one\one\hash\hash\hash\) and \(\one\hash\). Suppose we run them with some fixed but arbitrary word \(x\) in R1.
The first says “Go forward 2,” and the second “Add \(\one\) to R1.”
The first halts, while the second halts improperly.
Exercise 12
Which of the following programs halt when run on all empty registers? Which stop improperly? Why?
11###111###1####
11###111###11####
11###111###111####
1111###1111###1####11###11####
[It would be better to try to solve this problem without running the programs.]
Exercise 13
Exercise 12 was concerned with programs run on all empty registers. Find a program \(p\) and words \(w_1\), \(w_2\), and \(w_3\) so that
(a) When started with \(w_1\) in R1, \(p\) halts improperly.
(b) When started with \(w_2\) in R1, \(p\) halts improperly.
(c) When started with \(w_3\) in R1, \(p\) goes into an infinite loop inside \(p\).
Halting: the formal definitions¶
There are five ways that the run of a program \(p\) on some register contents could halt.
Instruction \(n\) of \(p\) (the last instruction) is of the form
1\(k\)#or1\(k\)##, and at some point in the run of \(p\), we reach this last instruction.Some instruction of \(p\), say instruction number \(i\), is of the form
1\(k\)###; and also \(i + k = n + 1\); and finally that at some point in the run of \(p\), we reach instruction \(i\).Instruction \(n\) of \(p\) (the last instruction) is of the form form
1\(k\)#####, and at some point in the run of \(p\), we reach this last instruction with Rk empty.Instruction \(n-1\) of \(p\) (the next-to-last instruction) is of the form form
1\(k\)#####, and at some point in the run of \(p\), we reach this instruction with Rk containing a word beginning with \(\one\).Instruction \(n-2\) of \(p\) (the second-to-last instruction) is of the form form
1\(k\)#####, and at some point in the run of \(p\), we reach this instruction with Rk containing a word beginning with \(\hash\).
Again, these are the formal conditions. Most of the time it is enough to work with the informal conditions that we started with: a program \(p\) halts on some inputs if at some point during the execution of \(p\) on the inputs, the control transfers to right below the last instruction of \(p\).