# 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. Oct 29, 2010 at 6:02
• I think Wolfram's equivalence principle is closer to physics than logic. Logicians seem to like to attack it for various reasons: it's not precise, it's not been proved, we can arrange things so it's false, etc. But in fact Wolfram is pointing out, in his own way, to a very interesting fact about computation, as it arises "in nature". Mar 28, 2014 at 6:19
• I don't know about cherry picking, the book seems pretty comprehensive to me, especially all those notes. Is there an a priori reason for not allowing changes of standard definitions? You're measuring with the wrong yardstick here. Wolfram is not doing math, at least not in the traditional sense of the word. Mar 28, 2014 at 7:10
• @Andrej, my main problem is that the statement is so vague that I don't see how it can make any verifiable/refutable predictions. And yes, if someone is changing the standard definitions just to be able to interpret what would not be a support for a claim as a support for the claim then I think it is problematic. Mar 28, 2014 at 7:20
• The statement is vague, but so what? It's not logic or math. It's an observation, supported by a thick book full of examples, that in nature "computational systems" tend to be either trivially simple or extremely sophisticated, and "equivalent" to each other. Rather than criticizing Wolfram for not talking the lingo of logic and math, it would be more productive to see that he has a point, and then formulate that point in whatever formalism your heart desires. But of course, if your heart desires no such thing, then you won't do it. Mar 28, 2014 at 7:28

I'm pretty sure the diagonalization argument applies to any model of computation which:

• can represent itself as a string, and
• can simulate another machine, given the above representation

If we had a model which violated one of the above conditions, its computational power would be extremely limited.

• 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). Oct 29, 2010 at 5:28

I'm not sure about the exact connection, but this seems related to the Friedberg-Muchnik theorem (see here): there is a r.e. set whose Turing degree is less than the halting problem. This result answered an influential question of Post and led to the introduction of the "priority method" in calculability.

Probably. There are many mathematical problems which probably include some among them, that are undecidable, i.e. answer is "yes" but no proof of that exists. For example the Collatz 3x+1 problem springs to mind as a candidate. Or the question of whether pi contains arbitrarily long strings of consecutive 9s. Any such problem could be regarded as a "model of computation" presumably much less powerful than a UTM, but it still would be undecidable whether it "halts" or whether it "always halts."

• I don't think this approach could work. See: for any such fixed statement, there exists an algorithm that decides if it is "true" or "false" in a finite amount of time, even when it is undecidable in ZFC (ref: en.wikipedia.org/wiki/Busy_beaver#Applications). On the other hand, if you consider as a model of computation the problem "given a statement, decide if it has a proof in ZFC", i think that model is Turing-complete. Jun 23, 2015 at 18:42