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?



Models of computation with decidable halting problem?
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.)


