Tell me more ×
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.
up vote 16 down vote favorite
4

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

2 Answers

up vote 12 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
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
up vote 3 down vote

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

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

so ... if we had a model which violated one of the above conditions, it's computational power would be extremely limited.

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

Your Answer

 
discard

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.