Take the 2-minute tour ×
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.

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|improve this question
it depends what you call "halting". If you allow it to enclose problems such as "does it halt on all words ?", then it is already undecidable for pushdown automata. –  Denis Mar 28 '14 at 15:26

3 Answers 3

up vote 16 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|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
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. –  Andrej Bauer Mar 28 '14 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. –  Kaveh Mar 28 '14 at 7:20

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

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.