tag:blogger.com,1999:blog-1793602440963329113.post4403694493058829097..comments2024-01-23T06:41:08.202-08:00Comments on Random thoughts and fancy math: The Single Rotation rule: remarkably simple and rich reversible cellular automatonDmitry Shintyakovhttp://www.blogger.com/profile/01405400371259506840noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-1793602440963329113.post-52841595922329300172023-12-09T15:41:56.527-08:002023-12-09T15:41:56.527-08:00@Anonymous, Morita recently constructed a reversib...@Anonymous, Morita recently constructed a reversible Turing machine in Double Rotate. (He formulates it as a partitioned cellular automaton, but I'm fairly sure that it's equivalent.) I think there though he handles the live cell conservation problem by initializing with infinitely many live cells (though in practice you just use as many as the amount of memory you need).<br /><br />Morita, Kenichi. "Making reversible computing machines in a reversible cellular space." Bulletin of EATCS 140, no. 2 (2023).<br /><br />(I would link it since the PDF is available online, but sometimes links run into trouble with spam detection.)Malcolm Sharpehttps://www.blogger.com/profile/16512148420655931251noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-24634675175472301872023-12-04T16:36:57.731-08:002023-12-04T16:36:57.731-08:00So if you actually built a universal Turing machin...So if you actually built a universal Turing machine this way, you'd start out with a standard pattern in a small area that is the FSM blob and the east blob close by. And the north blob would be a standard, finite pattern that is placed 2^n cells north of the main blob. This would then act like a Turing machine that started with an infinite tape that is mostly blank except the head is at the left end of a finite region of 1s and 0s, which are the binary representation of n. So the distance of 2^n cells encodes the integer n which encodes the initial bits on the tape. And it could then act exactly like that universal Turing machine running on that tape, so it could run arbitrarily long and write an arbitrary number of bits, possibly halting, or possibly never halting, depending on the chosen n.<br /><br />This is exactly the proof of the Turing completness of the Game of Life that I read in the 1980s. It assumed an infinite empty universe, with a number of active cells that is always below a fixed constant, but used the distances to two remote blobs to encode an arbitrary, growing tape. <br /><br />It would be very cool if that could be proved for this CA, too.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-80814349715507748262023-12-04T16:22:10.421-08:002023-12-04T16:22:10.421-08:00There were comments above that said you can't ...There were comments above that said you can't build a Turing Machine with a finite number of live cells. But that's not true.<br /><br />A Turing machine is a finite state machine plus a tape, where the tape can be finite length at each moment, but grow arbitrarily long as it is written to. But that's equivalent to a FSM plus two stacks (if you cut the tape at the head, and tilt each half up). And if you think of the stack as encoding a binary number, then that's equivalent to a FSM plus 4 counters, where a counter is a nonnegative integer that can grow arbitrarily large, and the FSM can increment, decrement, and check if it's zero. And that, in turn (by encoding as the product of powers of 4 primes) is equivalent to a FSM plus just 2 counters.<br /><br />So all you need is the ability to create two counters. There could be a main blob that is the FSM. Then a non-moving cycler that is far to the north, and another that is far to the east. If the FSM could shoot a spaceship at a blob that has the effect of moving it slightly farther away, or shoot a different spaceship that moves it slightly closer, and have a third interaction that detects whether it has retracted all the way back to the main blob, then this is equivalent to a FSM plus two counters. Which, in turn, is equivalent to a Turing machine.<br /><br />In other words, you don't need infinite live cells. You just need infinite space into which your two finite patterns can move. <br /><br />So the first step in building a Turing machine in this CA is to discover whether it is possible to have some pattern that oscillates in place, but when hit by some type of spaceship from a given direction, will interact with it and move slightly toward the direction the spaceship came from. And if there's another spaceship that would make it move slightly further away. Is this possible?<br /><br />I'm now very curious: is this CA Turing complete?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-68059844909699675872023-11-01T02:14:00.044-07:002023-11-01T02:14:00.044-07:00The "Double Rotate" rule is wonderful an...The "Double Rotate" rule is wonderful and deserves to be better known. Basically any reasonable low-entropy initialization spawns an incredible variety of spaceships (especially compared with the single common spaceship of Critters) until eventually settling into high-entropy generic configurations.<br /><br />Until trying Double Rotate, I thought that Critters was the most pleasing known reversible cellular automaton, what with it being one of the few that has a Wikipedia page, but now Double Rotate seems to me the clear champion.Malcolm Sharpehttps://www.blogger.com/profile/16512148420655931251noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-84402708773069870142022-01-01T00:21:18.482-08:002022-01-01T00:21:18.482-08:00تبلیغات رایگان
فروش مواد شیمیایی<a href="https://www.takro.net" rel="nofollow">تبلیغات رایگان</a><br /><a href="https://www.takro.net/category/349/Industry/362-Chemicals" rel="nofollow">فروش مواد شیمیایی</a>agahirayeganhttps://www.blogger.com/profile/07004724018990675781noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-7939343271062369232021-09-05T22:26:33.083-07:002021-09-05T22:26:33.083-07:00This comment has been removed by a blog administrator.John smith https://www.blogger.com/profile/03807718373407366299noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-68971087799661773092019-08-01T17:31:09.611-07:002019-08-01T17:31:09.611-07:00Finally, most definitions of Turing completeness t...Finally, most definitions of Turing completeness that I have seen allow for initial configurations with infinitely many live cells, as long as they have a short, finite description. For example, you could consider a starting configuration where all except a finite number of cells follow a periodic pattern. Such a configuration would avoid the problem Jennifer mentioned, but would still provide for Turing completeness under some definitions.Mason L. Greennoreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-67076549805049607532019-08-01T13:34:54.186-07:002019-08-01T13:34:54.186-07:00Also, any of the above rules that don’t contain in...Also, any of the above rules that don’t contain indestructible still lifes are candidates for physical universality. See https://www.scottaaronson.com/blog/?p=1896.Mason L. Greennoreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-24726536587905615982019-08-01T13:22:36.523-07:002019-08-01T13:22:36.523-07:00There is a hexagonal version (actually two of them...There is a hexagonal version (actually two of them) which uses the Q*Bert neighborhood. (If you’re not familiar with the Q*Bert neighborhood, see here: http://cell-auto.com/neighbourhood/qbert/index.html). In this version, if a single cell in a block is on, rotate it by 120 degrees clockwise. In the “Klein bottle invertible” version, you also rotate blocks with two on cells 120 degrees counterclockwise. The former example has inconstructible/indestructible still lifes (such as a star of six ON rhombi meeting at a point), the latter does not.<br /><br />For the regular Margolus neighborhood, one could also consider a rule in which every block is rotated by 90 degrees times the number of ON cells. Thus, blocks with 0 or 4 cells are unchanged, blocks with 1 on cell are rotated 90, blocks with 3 on cells are rotated 270, and (here’s where new behavior appears!) blocks with 2 cells of each type are rotated by 180. This rule is bound to give very different behavior from the ordinary single rotation rule, due to the frequency with which two-on, two-off blocks appear in most would-be spaceships.<br /><br />Finally, higher-dimensional versions could be worth considering. Using the four-dimensional version of the Margolus neighborhood, for example, you could have a rule with two different types of ON cell corresponding to rotations about two orthogonal planes (planes oriented so that rotations through them commute). Thus if a block has 1 red cell and 1 blue cell, it’s rotated 90 degrees in the “red” plane and 90 degrees in the orthogonal (“blue”) plane. A “purple” cell would count towards both planes, etc. The number of variations on this rule is practically endless. 4D works much better than 3D for these types of rules because in 3D there is no way to make rotations in different planes commute.Mason L. Greennoreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-42876938921262702342019-07-11T03:25:38.969-07:002019-07-11T03:25:38.969-07:00Thank you - Just shared this post with a colleague...Thank you - Just shared this post with a colleague who would benefit from reading this, really enjoyed it. <a href="https://elstel.org/coan/index.html.en" rel="nofollow">Compiler and Automaton Network Simulator</a>Elstelhttps://www.blogger.com/profile/08036491775830824447noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-9985446695933427382019-06-10T18:36:58.204-07:002019-06-10T18:36:58.204-07:00@Dmitry Shintyakov How hard would it be to add Kle...@Dmitry Shintyakov How hard would it be to add Klein bottle fields to the simulation?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-47312764815552769692019-05-27T10:34:03.047-07:002019-05-27T10:34:03.047-07:00@jennifer is right. With finite population there&#...@jennifer is right. With finite population there's no way that a reversable-CA could do the equivalent of writing to the Turing machine's infinite tape. @Henning's idea of encoding information by distance doesn't help because you'd run out of cells to encode those distances in addition to ever-increasing time needed to "read" those distances.Stephen Joneshttps://www.blogger.com/profile/17774967913434492343noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-80796054194217294542019-03-21T19:46:58.403-07:002019-03-21T19:46:58.403-07:00@jennifer I thought this too at first, but there c...@jennifer I thought this too at first, but there could be infinite many configurations from a given population as particles can travel arbitrary distances. You could encode information by distances. Henninghttps://www.blogger.com/profile/16298034713456050238noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-28320129907493081592019-03-21T18:46:30.072-07:002019-03-21T18:46:30.072-07:00@Henning: Call this a conjecture rather than a pro...@Henning: Call this a conjecture rather than a proof... I think the conservation of living cells implies a maximum finite memory for any given population of cells, and hence no truly Turing complete structures.Jennifer Rodriguez-Muellerhttps://www.blogger.com/profile/09407592439239791999noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-31346146973278418532019-02-20T01:31:55.481-08:002019-02-20T01:31:55.481-08:00Could this rule be turing complete? Could this rule be turing complete? Henninghttps://www.blogger.com/profile/16298034713456050238noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-76904143340225660852019-02-19T11:56:06.625-08:002019-02-19T11:56:06.625-08:00@Unknown, I think, I understand your idea.
Here is...@Unknown, I think, I understand your idea.<br />Here is a link to the simulator with this rule (I also initialized half of the field with alive cells):<br /><br />http://dmishin.github.io/js-revca/?rule=0,2,8,3,1,5,6,13,4,9,10,7,12,14,11,15&rle_x0=30&rle_y0=0&rle=33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o&step=8&frame_delay=100&size=64x64&cell_size=4,1&phase=0<br /><br />On the first glance, it is not much different. There are no indestructible still lifes though.Dmitry Shintyakovhttps://www.blogger.com/profile/01405400371259506840noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-45241544191671008652019-02-17T21:13:25.655-08:002019-02-17T21:13:25.655-08:00Have you considered this slight variation: rotate ...Have you considered this slight variation: rotate blocks with exactly 3 alive cells *counter*clockwise 90°.<br /><br />Why would such a rule be interesting? The reason is that we can use *local orientations* as cell states. Then the two rules can be seen as one rule as follows:<br /><br />Rule: In a block, if there is exactly one cell of a given orientation in that block, rotate the block 90 degrees clockwise, using that orientation's definition of clockwise.<br /><br />If we are on an orientable surface (like the plane or torus) this is not particularly interesting, but if we are on a *non*orientable surface (like a mobius strip or a klein bottle), it is pretty neat. When a surface is nonorientable, there is no globally consistent orientation. That means that if a spaceship, for example, loops around the space, it will actually be in the opposite state of what it started as.Anonymoushttps://www.blogger.com/profile/15656306820964021990noreply@blogger.comtag:blogger.com,1999:blog-1793602440963329113.post-49359944423906438402019-02-16T11:12:39.753-08:002019-02-16T11:12:39.753-08:00Margouls should be spelled "Margolus" th...Margouls should be spelled "Margolus" throughoutwon3dhttps://www.blogger.com/profile/09787472194187459747noreply@blogger.com