Cris and I once presented Wolfram with an example that appears to be of strictly intermediate complexity (mentioned in his big book), involving carries. We got him to admit that it seemed to be strictly intermediate, but he insisted that it was the exception rather than the rule. So it seems that when pressed, Wolfram admits that his Principle of Computational Equivalence isn’t as strictly dichotomous as advertised. Jim Propp On Tue, Oct 1, 2019 at 7:49 PM Cris Moore via math-fun < math-fun@mailman.xmission.com> wrote:
The Baker’s map would fill this bill — symbolically it’s equivalent to a simple shift, like a turing machine that just cruises in one direction and doesn’t modify any symbols on the tape. Indeed this was a starting point for my Ph.D. thesis, since squashing, squeezing, and translating parts of the unit square (and thus reading and writing symbols, and shifting left or right) can simulate Turing machines.
- Cris
On Oct 1, 2019, at 5:16 PM, James Propp <jamespropp@gmail.com> wrote:
Is it possible that one could design a system that in some sense is provably chaotic but also in some sense is provably not Turing complete?
Jim Propp
On Tue, Oct 1, 2019 at 5:43 PM Allan Wechsler <acwacw@gmail.com> wrote:
I remain skeptical. That "more regular" texture is periodic only along leftward speed-of-light diagonals. The period doubles occasionally as you go deeper into the pattern, and never seems to decrease. There seems to be no pattern at all perpendicular to that diagonal. And this "slightly regular" regime loses ground to chaos at the right edge. I don't see how anything could conceivably be "built" there.
All these observations seem to suggest something that Wolfram appears reluctant to acknowledge: that a system can display chaotic behavior, but not be a usable medium of computation.
On Tue, Oct 1, 2019 at 4:48 PM Tomas Rokicki <rokicki@gmail.com> wrote:
I believe with an appropriate infinite "background" you can do some engineering in rule 30. Suitable backgrounds might be visible in the more regular side of the default evolution of a single cell.
On Tue, Oct 1, 2019 at 1:42 PM Allan Wechsler <acwacw@gmail.com> wrote:
Follow-up on my last post. I don't know why I never realized this before, but I now think that vulnerability at the left edge of a periodic region is inescapable: the left boundary of such a region always moves rightwards (encroaching on the periodic region) at the speed of light. This is because a change to the leftmost cell of a three-cell neighborhood always changes the fate of the center cell.
I can't articulate why, but I am pretty sure that means you can't do much useful "engineering" in Rule 30. Such engineering always seems to involve "structures" of some sort moving around and interacting. How can you build anything like that with no stable regimes?
On Tue, Oct 1, 2019 at 4:17 PM Allan Wechsler <acwacw@gmail.com> wrote:
Having played a bit with rule 30 in the past, I have what I think is a less ambitious question that Wolfram's very hard three.
Can a periodic regime take over territory leftward? In every example I have observed, periodic regimes are always vulnerable to incursion by chaos at their left borders. As one of Wolfram's figures shows, some periodic regimes can conquer chaos, but only in a rightward direction.
On Tue, Oct 1, 2019 at 3:31 PM James Propp <jamespropp@gmail.com> wrote:
https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes
> _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun