26
$\begingroup$

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

Improve this question
$\endgroup$
0

4 Answers 4

Reset to default
18
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ mmm, let's say a model is Turing-complete iff it can simulate an UTM. $\endgroup$
    – didest
    Oct 29, 2010 at 6:02
  • 1
    $\begingroup$ 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". $\endgroup$
    – Andrej Bauer
    Mar 28, 2014 at 6:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Mar 28, 2014 at 7:10
  • 4
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Mar 28, 2014 at 7:20
  • 4
    $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Mar 28, 2014 at 7:28
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 10
    $\begingroup$ 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). $\endgroup$
    – Kaveh
    Oct 29, 2010 at 5:28
2
$\begingroup$

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.

Improve this answer
$\endgroup$
-2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – didest
    Jun 23, 2015 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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