Naszvadi wrote:calcyman wrote:...
If you want Banks-I and Rule 110 to be universal, then specifying the pattern as a predicate in Presburger arithmetic is one solution, but it feels very arbitrary.
Suggesting that Cook's result (tag systems in Rule-110) needs clarification or revocation?
Cook's paper is absolutely fine; he specifically writes:
Matthew Cook wrote:given a fixed repeating pattern to the left and right, it is undecidable whether a given finite initial condition will lead to periodicity in Rule 110’s behavior
My criticism is not with Cook's result, but with people who go on to say "rule 110 is universal" without explaining what "universal" means in this context.
Naszvadi wrote:In order to raise all your 2cents, according to your interpretations and assumptions: even rule-72 is universal, if a binary fraction constant "z" is known, where its nth digit is 1 if and only if the nth Turing machine halts on the empty input. The cellspace is initially filled with ones in all (4*k)th positions if z's kth digit is 1. Then let the initial generation be altered in position ((4*n)+1). So the fate of any kind of pattern is equivalent to determine a Turing machine's execution finiteness.
Yes, that's why it's necessary to restrict the function mapping a Turing machine to the input pattern.
That function should be computable (as otherwise it could determine directly whether the TM halts), which implies that the output must be a finite description. The simplest set of finitely-describable patterns are the finite patterns themselves. You could, as Cook does, use a more complex definition such as 'patterns which agree with a periodic background in all but finitely many cells', but this needs specifying explicitly to contrast it with the stronger notion of universality that Banks-IV, JVN29, Codd, and B3/S23 all possess.
As far as I know, it's unsolved whether Rule 110 is universal in the stronger sense.
I've heard on internets that you are a mathematician withOUT any pejorative prefixes like appl./programmer etc.
Just like me.
Indeed -- which is perhaps why I'm very cautious about ensuring that when we use 'universal', everyone agrees what it means. I recall that there was (maybe in the 1800s) a mathematical journal that published (inter alia) two papers on real analysis, where the result of the first directly contradicted the result of the second; specifically, the word 'function' hadn't been properly defined at that point, and the two authors were using different definitions.
And in classical logic, a single contradiction causes everything to collapse:
https://en.wikipedia.org/wiki/Principle_of_explosion