Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 18 down vote accepted

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

share|cite|improve this answer
mmm, let's say a model is Turing-complete iff it can simulate an UTM. – Diego de Estrada Oct 29 '10 at 6:02
Thank you very much! – Diego de Estrada Oct 29 '10 at 6:33
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". – Andrej Bauer Mar 28 '14 at 6:19
@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. – Kaveh Mar 28 '14 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. – Andrej Bauer Mar 28 '14 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.

share|cite|improve this answer
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

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.

share|cite|improve this answer

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

share|cite|improve this answer
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: 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. – Diego de Estrada Jun 23 '15 at 18:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.