Halting

Halting#

1# has programs which contain infinite loops such as

111###111####

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.

Halting: informally#

Definition

We (informally) say that a program $p$ halts on some inputs if at some point during the execution of $p$ on those 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: 11###1# and 1#11###. Suppose we run them with some fixed but arbitrary word $x$ in R1.

The first says “Go forward 2,” and the second “Add 1 to R1, and then advance two instructions.”

The first halts, while the second halts improperly.

Exercise 35

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 36

Exercise 35 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 definition#

Definition

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$# or 1^$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 1.
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 #.

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$.

Up-arrow and down-arrow notation#

Definition

We write $[\![p]\!](\ )\!\!\downarrow$ to mean that $p$ is a program, and running $p$ on all empty registers eventually halts.

We write $[\![p]\!](\ )\uparrow$ to mean that $p$ is a program, and running $p$ on all empty registers does not eventually halt: the computation either goes on forever or comes to an improper halt.

We write $[\![p]\!](x)\!\!\downarrow$ to mean that $p$ is a program, and running $p$ with $x$ in R1 and all other registers empty eventually halts.

We write $[\![p]\!](x)\uparrow$ to mean that $p$ is a program, and running $p$ with $x$ in R1 and all other registers empty does not eventually halt (as above).

The definitions of $[\![p]\!](x_1, \ldots, x_n)\!\!\downarrow$ and $[\![p]\!](x_1, \ldots, x_n)\!\!\uparrow$ are similar.

The halting problem#

We now can state one of the key foundational points in computability theory. This is that the halting problem is unsolvable. It is a result due to Alan Turing in his seminal paper of 1936. Although his original paper dealt with what we now call Turing machines (indeed, they were originated in this same paper), the discussion carries over to register machines.

We begin by thinking about 1# programs $x$ and asking whether they halt or not. As we know, it makes a difference whether we run $x$ on all empty registers or with some non-empty words in the registers. Let us for a moment just consider $x$ on all empty registers. It might be nice to know if $x$ halts or not. Of course we mean “halting” according to our formal definition. In computability theory, we always ask if

Halting Problem

Is there a program $p$ such that for all programs $x$,

\[\begin{split} [\![p]\!](x) = \left\{ \begin{array}{ll} \one & \mbox{if $[\![x]\!](\ )\!\!\downarrow$} \\ \hash & \mbox{if $[\![x]\!](\ )\!\!\uparrow$} \\ \end{array} \right. \end{split}\]

So the problem here is the set of programs which halt on empty registers. Turing showed that this problem is unsolvable. That is, there is no program $p$ as described.

For programs with an input, the statement of the problem is similar. We need to fix a number of arguments. Let’s fix this to be $1$. We are considering programs $x$ and their run on one word. Then we would be asking if there is a program $p$ such that

\[\begin{split} \begin{array}{lcl} [\![p]\!](x,y) & = & \left\{ \begin{array}{ll} \one & \mbox{if $[\![x]\!](y)\dar$}\\ \hash & \mbox{if $[\![x]\!](y)\uparrow$} \end{array} \right. \end{array} \end{split}\]

Although it appears much later in this book, you could read Theorem 11 right now.

Halting

Contents

Halting#

Halting: informally#

Halting: the formal definition#

Up-arrow and down-arrow notation#

The halting problem#