# Is there a non Turing-complete model of computation whose halting problem is undecidable?

I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton?

This would almost disprove Wolfram's "Principle of Computational Equivalence":

Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication

-

You can easily build artificial models which are not Turing complete but the halting problem for them is undecidable. E.g. take all TMs that do not halt on anything but $0$.

### Regarding the statement:

You cannot disprove a statement that is not precise enough. Almost none of the words in the statement is well-defined (please provide the definition for them if this is not the case).

-
mmm, let's say a model is Turing-complete iff it can simulate an UTM. –  Diego de Estrada Oct 29 '10 at 6:02
I can easily modify it such that it would be obvious it cannot simulate UTM. –  Kaveh Oct 29 '10 at 6:11
Now it is modified. –  Kaveh Oct 29 '10 at 6:29
Thank you very much! –  Diego de Estrada Oct 29 '10 at 6:33
You are welcome. –  Kaveh Oct 29 '10 at 6:44
You have to be able to effectively enumerate the machines, simulate them, and compute some function with the property $\forall x. f(x) \neq x$. But diagonalization will only show the halting problem for this model cannot be decided by the machines in the model, it does not mean that it will be undecidable (by Turing machines). –  Kaveh Oct 29 '10 at 5:28