Models of computation with decidable halting problem?

Question

There are numerous examples of models of computation in which all programs halt, for example primitive recursion.

Are there (non-trivial) examples of models in which only some programs halt, but the halting problem is still decidable?

Does the decision procedure need to lie outside of the original model itself?

EDIT:

Carl Mummert gives very good example of a model of computation that has this property. But the example of polynomially clocked Turing machines is weaker than primitive recursion.

Are there examples which are stronger than primitive recursion?

Answer 1

Joel Hamkins points out that the decision procedure for any reasonable notion of "computability" is not going to be solvable by a function that is "computable" within that notion.

Here is a contrasting example of a nontrivial model of computation in which the halting problem is solvable in the usual sense of computation. An index $e$ in our new system is a pair $(e_1, p)$ where $e_1$ is an index for a Turing machine and $p$ is a code for a polynomial over $\mathbb{N}$. In our new system, program $e$ is said to compute output $o$ on input $n$ (write $P_e(n) = o$) if and only if Turing machine $e_1$ computes $o$ on input $n$ in less than $p(|n|)$ steps. If $e_1$ runs for more then $p(|n|)$ steps then we say the computation of $P_e(n)$ is undefined (i.e. does not halt). Here we assume the Turing machine uses binary coding for numbers and we let $|n|$ be the number of bits required to express $n$ in binary notation.

This restricted model of computation is relatively common in the study of polynomial-time computability, where an index of the form $e = (e_1, p)$ is called a "polynomially clocked Turing machine". It's immediate from the definitions that a function is computable in the restricted model if and only if it is computable in polynomial time. Thus the model includes a very wide class of functions. However, because the time bound for index $e$ is already included in $e$, we can solve the halting problem for this model of computation with a normal Turing machine. (We cannot solve it with any polynomially clocked machine, of course.)

Answer 2

The classical proof that the halting problem is undecidable is extremely flexible and applies to innumerable non-classical models of computability.

The argument goes like this. Suppose that we have a notion of computability, by which a program $p$ on some input $x$ leads, when halting, to an output $y$. The halting problem is the question of determining which pairs $(p,x)$ do in fact lead to an output $y$. Suppose within this system we had a way to compute this. Then consider the following process. Design a "program" such that on input $q$, it determines whether $q$ halts on input $q$, and if so, our algorithm does the opposite. Now, if our algorithm is implemented by program $p$, then $p$ halts on $p$ if and only if it doesn't, a contradiction.

The argument applies to any model of computability that is able to implement this process, and this includes numerous instances: computability on Turing machines, register machines, oracle computability, polynomial-time computability, infinite time computability, and on and on and on.

Any abstract notion of computability that has sufficient universality ("run program $q$ on input $q$") and nontrivial branching ("do the opposite") capabilities will be able to implement the algorithm, and will therefore have an undecidable halting problem.

Meanwhile, let me mention that for some models of computability, the various versions of the halting problem that are equivalent in the classical computability context become inequivalent. For example, in ordinary Turing computability, it doesn't matter whether you describe the halting problme as the membership problem of the set $\{p\mid \varphi_p(0)\downarrow\}$ of programs that halt on trivial input or as the membership problem of the set $\{(p,x)\mid \varphi_p(x)\downarrow\}$ of program/input pairs that halt; it doesn't matter because these two sets are reducible to one another and have the same Turing degree. But the analogous fact is not true for all models of computability. For example, the theory of infinite time Turing machines, where one has two jump operators, corresponding to the lightface and the boldface halting problems, and these are not infinite-time computably equivalent. A similar situation arises in higher recursion theory.

Finally, let me mention the theory of infinite time register machines, which approaches an example of the phenomenon that you request. These machines extend the operation of ordinary register macines into transfinite ordinal time, in a way analogous to the infinite time Turing machines. Nevertheless, it turns out that for the ITRMs, there is no universal machine, and indeed, this is a consequene of the fact that for each finite $n$, the $n$-register halting problem for ITRMs is in fact ITRM decidable. (One needs more than $n$ registers to do it.) This phenomenon definitely does not occur in the classical finite time theory, since once one has sufficiently many registers, the model of computability is fully powerful for classical computability. For the infinite time theory, however, adding more registers continues to make the model of computability stronger, with the halting problem for the smaller machines becoming decidable by the larger machines.