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

<ul>
<li>can represent itself as a string, and</li>
<li>can simulate another machine, given the above representation</li>
</ul>

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

CC BY-SA 2.5
2010-10-29T05:28:18.897Z
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
CC BY-SA 3.0
2010-10-29T03:46:32.200Z
2014-03-27T23:47:18.427Z
2014-03-27T23:47:18.427Z
gabgoh
<p>I'm not sure about the exact connection, but this seems related to the Friedberg-Muchnik theorem (see <a href="http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_and_the_priority_method" rel="nofollow">here</a>): 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.</p>

CC BY-SA 3.0
2014-03-28T00:07:03.087Z
2014-03-28T00:07:03.087Z
Super0
<p>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."</p>

CC BY-SA 3.0
2015-06-23T18:42:45.430Z
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: https://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.
didest
CC BY-SA 3.0
2015-06-23T17:33:00.673Z
2015-06-23T17:33:00.673Z
Warren D. Smith
<p>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 <span class="math-container">$0$</span>.</p>
<h3>Regarding the statement:</h3>
<p>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).</p>

CC BY-SA 3.0
2014-03-28T06:19:59.090Z
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
CC BY-SA 3.0
2014-03-28T07:10:29.460Z
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
CC BY-SA 3.0
2014-03-28T07:20:01.357Z
@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
CC BY-SA 3.0
2014-03-28T07:28:31.593Z
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
CC BY-SA 3.0
2014-03-28T07:52:58.257Z
@Andrej, sorry but I am really not interested in arguing about this. I stated the main issue I have with the statement and will stop with drawing your attention to the emphasis on "so" in my previous comment and its following sentence.
Kaveh
CC BY-SA 2.5
2010-10-29T06:02:30.937Z
mmm, let's say a model is Turing-complete iff it can simulate an UTM.
didest
CC BY-SA 2.5
2010-10-29T05:54:42.100Z
2010-10-29T06:11:48.830Z
2020-06-17T09:38:08.363Z
Kaveh
<p>I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton?</p>

<p>This would <em>almost</em> disprove Wolfram's "Principle of Computational Equivalence":</p>

<blockquote>
  <p>Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication</p>
</blockquote>

<automata-theory><computability><turing-machines><lambda-calculus><universal-computation>
Is there a non Turing-complete model of computation whose halting problem is undecidable?
didest
# Is there a non Turing-complete model of computation whose halting problem is undecidable?

(Asked by: username_0 on 2010-10-29)

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

**Tags:** automata-theory, computability, turing-machines, lambda-calculus, universal-computation

---

## 4 answers

### Answer by username_2 on 2010-10-29. Score: 18 | Accepted answer

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

> **Comments:**
> **username_0**: mmm, let's say a model is Turing-complete iff it can simulate an UTM.  
> **username_5**: 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".  
> **username_5**: 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.  
> **username_2**: @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.  
> **username_5**: 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.  
> **username_2**: @Andrej, sorry but I am really not interested in arguing about this. I stated the main issue I have with the statement and will stop with drawing your attention to the emphasis on "so" in my previous comment and its following sentence.  

---

### Answer by username_1 on 2010-10-29. Score: 4

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.

> **Comments:**
> **username_2**: 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).  

---

### Answer by username_3 on 2014-03-28. Score: 2

I'm not sure about the exact connection, but this seems related to the Friedberg-Muchnik theorem (see [here](http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_and_the_priority_method)): 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.


---

### Answer by username_4 on 2015-06-23. Score: -2

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

> **Comments:**
> **username_0**: 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: https://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.  

---

