0
$\begingroup$

My supposition is that this is was more or less an automatic designation based on the fact that Rule 110 requires an infinite "background tiling" of the 14-bit sequence 00010011011111, and since by convention a proper Turing-complete system is supposed to begin with a blank tape or its equivalent, this doesn't count.

I would understand the argument for "weakly" universal if the tiling sequence was dependent on the program in some way, but that's not the case here. In fact, as near as I can tell, within the mathematical universe of Rule 110, that sequence is the blank tape.

(The staggered small triangle tiling is what this sequence looks like on a typical plot.)

example pic

If you start with virtually any aperiodic seed row (e.g. a few random bits on top of a 0 tiling), the system invariably settles into a state where the obvious background is that sequence. It's the sequence of least resistance, sort of the lowest-energy vacuum state of the Rule 110 universe. On top of that, it's a constant finite overhead, which already to me seems like suspect grounds for the "weakly" qualifier.

Is there a good reason for this designation that I've missed or something I've misunderstood?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Can you cite your sources? Where did you find it characterized as weakly universal? What definition of weakly universal did they provide? I don't see any such claim in the link you provided. I suspect you might be attaching meaning to the phrase "weakly universal" that was not intended. In mathematics, we often define phrases in some precise way that doesn't necessary correspond to the standard English meaning of the individual words. If you search-and-replace "weakly universal" with "frobbigadinous", it will have the same mathematical meaning, and it might answer your question. $\endgroup$
    – D.W. ♦
    Dec 12, 2022 at 0:29

2 Answers 2

Reset to default
1
$\begingroup$

Universality of Turing machines and Turing completeness of arbitrary computational systems are two different things. There is a concept of a weakly universal Turing machine, but no analogous concept of weak Turing completeness.

The question that you linked in your answer is about a Turing machine that simulates a rule-110 cellular automaton. That Turing machine is weakly universal. The rule-110 system that it simulates is Turing complete, but it is not weakly universal, since it isn't a Turing machine.

Improve this answer
$\endgroup$
0
$\begingroup$

Thanks to D.W., I searched for sources, and started to find plenty of references (many on comments on stackexchange, some papers), but eventually came to

https://math.stackexchange.com/questions/1609858/how-are-weakly-universal-turing-machines-actually-defined

This answers my question inasmuch as it directly discusses all this nonsense, and seems to reaffirm my understanding that R110 is universal in every reasonable sense of the word, no qualifiers needed.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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