The Turing machine

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Post Reply
User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

The Turing machine

Post by gameoflifemaniac » September 7th, 2017, 11:15 am

How to use the (universal) Turing machine in Conway's Game of Life?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: The Turing machine

Post by dvgrn » September 7th, 2017, 12:35 pm

gameoflifemaniac wrote:How to use the (universal) Turing machine in Conway's Game of Life?
Start with Paul Rendell's pages. The one I've linked to might have the biggest variety of detail collected in one place. Follow the various links and you'll eventually understand how to change the program (if you still want to), using the Python script in the downloadable ZIP file.

There's a more recent version with a continuously growing stack. This fulfills the technical requirement that a Turing machine should have an unlimited tape... but it's more complicated, so it runs slower in Golly.

To get the idea of how the Life Turing machine works you don't actually need the unlimited tape. So I've linked to a limited-tape version above, rather than the "latest and greatest".

Depends on What You Mean By "Use"...
The thing is, Turing machines are most useful as a theoretical construct -- a relatively simple model that can provably calculate anything that can be calculated.* That doesn't mean that you'd really want to "use" it in practice, most of the time! The sample program described in the link takes a significant amount of Golly time to make a duplicate copy of a binary string.

The Life Turing machine could be programmed to calculate, say, the digits of pi -- but the program would be hideously long, there's no display component to allow for a visible decimal readout, and it would probably take Golly hundreds of years and an unlikely amount of memory to calculate just the first few digits.

It's a little more complicated to prove that Calcyman's pi calculator can be adjusted to do other arbitrary calculations, and much more of a headache to explain how exactly it should be done -- there's no published script to create Calcyman-style calculators with arbitrary programs. But it's a good example of a hard-wired special-purpose logic circuit, and so it's many, many orders of magnitude faster than an implementation based on a Turing machine.

* (unless you agree with Selim Akl, but that's a rabbit hole I don't think you need to go down at this point...)

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: The Turing machine

Post by simsim314 » September 12th, 2017, 2:17 pm

I was thinking about turing machine compiler based on Geminoids.
The basic idea is to add SLs to Demonoid to simulate turing rules. The tape will consist of SLs on different "relative" lanes, and the "head state" will be defined by active "reflective array of SLs".

Rule is a combination of Head state + SL of the tape . So for each Head state we will have special "array" that will reflect a glider from the tape into a different "path". The actions are also quite simple: define move left or right (the demonoid will need to be modified to support left and right movement), new head state (by deleting all reflective arrays which do not correspond to the state). And finally placing the tape SL once again in the new place defined by the rule. Every operation should be done once only, so the reading operation is destructive.

I'm thinking taking some turing machine syntax from here and make a script that compiles it into GOL state.

The only problem I can find in this plan except the execution, is that geminoids tend to work slowly, so the turing process will not be fun to observe. Anyway I think it will be the most "visually appealing" and simplistic universal computation simulator, the mechanism of which is also quite simple to understand.

Maybe it should be first done in GeminoidParticle rule where the design pattern is much more clear.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: The Turing machine

Post by dvgrn » September 12th, 2017, 3:33 pm

simsim314 wrote:...(the demonoid will need to be modified to support left and right movement)...
On balance that probably counts as a redesign from the ground up, not a modification. You'll probably have to replace all the circuitry in current Demonoids and then add ten times more, to implement a Turing machine that can move either left or right depending on external signals.

Seems like a device like that would have less in common with Demonoids than with the linear propagator. But that's old technology now -- pre-single-channel and pre-slow-salvo-Snark. It would be interesting to see how much smaller that kind of movable/copiable loop could be made these days.
simsim314 wrote:The only problem I can find in this plan except the execution, is that geminoids tend to work slowly, so the turing process will not be fun to observe. Anyway I think it will be the most "visually appealing" and simplistic universal computation simulator, the mechanism of which is also quite simple to understand.
We could make a diamond-shaped Geminoid Turing machine that would work fairly quickly in Golly, I think -- I don't know how much quicker, but probably a couple of orders of magnitude faster than the Demonoids anyway.

It will require solving some technical timing problems involving either Corderships or *WSS+G collisions, to make new faraway targets that can be turned into 90-degree corners. But at least at the moment it seems doable.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: The Turing machine

Post by simsim314 » September 12th, 2017, 5:33 pm

I had some simplifying idea. Think that we could build a mechanism that has internal logic in it - that works like turing machine (i.e. all the triggers for head-tape states). All we need is a gun - that shoots the same slow salvo construction over and over again - and our output needs to be the construction block moved by some delta. This is basically slider gun that shoots Turing machine logic circuitry.

One point to notice here is that this infinite tape turing machine can be extended to only one side - the other side is limited by the gun "core", this is still universal and much the same for most purposes.

This will also allow us to focus on the turing circuitry which is the most interesting I think, and should work better in golly.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: The Turing machine

Post by dvgrn » September 12th, 2017, 9:31 pm

simsim314 wrote:I had some simplifying idea. Think that we could build a mechanism that has internal logic in it - that works like turing machine (i.e. all the triggers for head-tape states). All we need is a gun - that shoots the same slow salvo construction over and over again - and our output needs to be the construction block moved by some delta. This is basically slider gun that shoots Turing machine logic circuitry.
Ah, that's much better than a loop structure that has to move itself. Very nice! Will be interested to see what shortcuts might show up for encoding different states on the tape.
simsim314 wrote:One point to notice here is that this infinite tape turing machine can be extended to only one side - the other side is limited by the gun "core", this is still universal and much the same for most purposes.
I'm not quite sure about this yet. The link you gave seems to be simulating two-way infinite Turing machines, and if I remember right those are quite a bit more straightforward to program than machines with one-sided infinite tapes. To prove that a one-sided tape is universal, don't you have to do something awful like pretend the odd tape locations are negative, and only the even ones are positive?

I suspect we could put together a two-way infinite Turing Machine run by a single gun, with a little more work. Maybe a piece of stable circuitry can sit at the zero point on the tape, and whenever the Turing machine tries to move left from 0, or right from -1, it notices that, closes the [positive|negative] output from the gun loop, and opens a different [negative|positive] one. The negative side of the tape doesn't even have to be quite contiguous with the positive side, as long as there's enough space in the gun loop to give the switching circuitry time to work.

Even with that extra complication in the mechanism, a two-way tape Turing machine might be more intuitive -- easier to put real programs into and get understandable results out.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: The Turing machine

Post by simsim314 » September 13th, 2017, 3:14 am

dvgrn wrote:what shortcuts might show up for encoding different states on the tape.
I was thinking of SL, triggered by glider - and the lane of the returning glider will collide with "rule reflector array", that outputs different stuff depending on the input-tape lane.
dvgrn wrote:To prove that a one-sided tape is universal, don't you have to do something awful like pretend the odd tape locations are negative, and only the even ones are positive?
Yes this is "straight proof" but you can easily prove existence of universal one sided turing machine, which is capable to simulate any other one sided turing machine, by placing the instruction commands table near the root.

-----

Anyway I was thinking about several guns as much as number of reading head states, which build the reflection array and rule table according to the head state, and other guns are blocked by eaters.

Except the building of special reflective array per head statem, we need to build a unit that can output the following:

1. Eaters placed to the left or right + single eater skipped
2. Tape SL in any possible state

Everything should also be possible to destruct regardless if they were used for logic or not. Static circuit with self destruct will work but is real overkill.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: The Turing machine

Post by simsim314 » September 13th, 2017, 6:24 am

Here is the basic building block of this design:

Code: Select all

x = 268, y = 269, rule = LifeHistory
2A$2A2$18.A$17.A.A$17.A2.A$18.2A5$15.2A$15.A.A$11.2A3.A.A$10.A.A4.A$
11.A8$38.A$37.A.A$37.A2.A$38.2A5$35.2A$35.A.A$31.2A3.A.A$30.A.A4.A$
31.A8$58.A$57.A.A$57.A2.A$58.2A5$55.2A$55.A.A$51.2A3.A.A$50.A.A4.A$
51.A8$78.A$77.A.A$77.A2.A$78.2A5$75.2A$75.A.A$71.2A3.A.A$70.A.A4.A$
71.A5$135.A$135.A.A$135.2A$98.A$97.A.A$97.A2.A$98.2A5$95.2A$95.A.A$
91.2A3.A.A$90.A.A4.A$91.A8$118.A$117.A.A$117.A2.A$118.2A5$115.2A$115.
A.A$111.2A3.A.A$110.A.A4.A$111.A8$138.A$137.A.A$137.A2.A$138.2A5$135.
2A$135.A.A$131.2A3.A.A$130.A.A4.A$131.A8$158.A$157.A.A$157.A2.A$158.
2A5$155.2A$155.A.A$151.2A3.A.A$150.A.A4.A$151.A8$178.A$177.A.A$177.A
2.A$178.2A5$175.2A$175.A.A$171.2A3.A.A$170.A.A4.A$171.A8$198.A$197.A.
A$197.A2.A$198.2A5$195.2A$195.A.A$191.2A3.A.A$190.A.A4.A$191.A8$218.A
$217.A.A$217.A2.A$218.2A5$215.2A$215.A.A$211.2A3.A.A$210.A.A4.A$211.A
51$265.3A$265.A$266.A!
EDIT
Signal duplicator with self destruct:

Code: Select all

x = 622, y = 791, rule = LifeHistory
149.2A$149.2A2$167.A$166.A.A$166.A2.A$167.2A5$164.2A$164.A.A$160.2A3.
A.A$159.A.A4.A$160.A21$146.C$145.C.C3.2C$145.C.C2.C2.C$146.C4.2C4$
207.A$206.A.A$206.A2.A$207.2A5$204.2A$204.A.A$200.2A3.A.A$199.A.A4.A$
200.A21$186.C$185.C.C3.2C$185.C.C2.C2.C$186.C4.2C4$247.A$246.A.A$246.
A2.A$247.2A5$244.2A$244.A.A$240.2A3.A.A$239.A.A4.A$240.A4$385.A$385.A
.A$385.2A15$226.C$225.C.C3.2C$225.C.C2.C2.C$226.C4.2C4$287.A$286.A.A$
286.A2.A$287.2A5$284.2A$284.A.A$280.2A3.A.A$279.A.A4.A$280.A21$266.C$
265.C.C3.2C$265.C.C2.C2.C$266.C4.2C4$327.A$326.A.A$326.A2.A$327.2A5$
324.2A$4.2A318.A.A$4.2A314.2A3.A.A$319.A.A4.A$22.A297.A$21.A.A$21.A2.
A$22.2A5$19.2A$19.A.A$15.2A3.A.A$14.A.A4.A$15.A9$306.C$305.C.C3.2C$
305.C.C2.C2.C$306.C4.2C4$367.A$366.A.A$366.A2.A$367.2A2$.C$C.C3.2C$C.
C2.C2.C$.C4.2C356.2A$364.A.A$360.2A3.A.A$359.A.A4.A$62.A297.A$61.A.A$
61.A2.A$62.2A5$59.2A$59.A.A$55.2A3.A.A$54.A.A4.A$55.A9$346.C$345.C.C
3.2C$345.C.C2.C2.C$346.C4.2C4$407.A$406.A.A$406.A2.A$407.2A2$41.C$40.
C.C3.2C$40.C.C2.C2.C$41.C4.2C356.2A$404.A.A$400.2A3.A.A$399.A.A4.A$
102.A297.A$101.A.A$101.A2.A$102.2A5$99.2A$99.A.A$95.2A3.A.A$94.A.A4.A
$95.A9$386.C$385.C.C3.2C$385.C.C2.C2.C$386.C4.2C4$447.A$446.A.A$446.A
2.A$447.2A2$81.C$80.C.C3.2C$80.C.C2.C2.C$81.C4.2C356.2A$444.A.A$440.
2A3.A.A$439.A.A4.A$142.A297.A$141.A.A$141.A2.A$142.2A5$139.2A$139.A.A
$135.2A3.A.A$134.A.A4.A$135.A9$426.C$425.C.C3.2C$425.C.C2.C2.C$426.C
4.2C4$487.A$486.A.A$486.A2.A$487.2A2$121.C$120.C.C3.2C$120.C.C2.C2.C$
121.C4.2C356.2A$484.A.A$480.2A3.A.A$479.A.A4.A$182.A297.A$181.A.A$
181.A2.A$182.2A5$179.2A$179.A.A$175.2A3.A.A$174.A.A4.A$175.A9$466.C$
465.C.C3.2C$465.C.C2.C2.C$466.C4.2C4$527.A$526.A.A$526.A2.A$527.2A2$
161.C$160.C.C3.2C$160.C.C2.C2.C$161.C4.2C356.2A$524.A.A$520.2A3.A.A$
519.A.A4.A$222.A297.A$221.A.A$221.A2.A$222.2A5$219.2A$219.A.A$215.2A
3.A.A$214.A.A4.A312.3A$215.A318.A$535.A$503.C$502.C.C$503.2C3$507.2C$
506.C2.C$507.2C12$201.C$200.C.C3.2C$200.C.C2.C2.C$201.C4.2C4$262.A$
261.A.A$261.A2.A$262.2A5$259.2A$259.A.A$255.2A3.A.A$254.A.A4.A$255.A
21$241.C$240.C.C3.2C$240.C.C2.C2.C$241.C4.2C4$302.A$301.A.A$301.A2.A$
302.2A5$299.2A$299.A.A$295.2A3.A.A$294.A.A4.A$295.A21$281.C$280.C.C3.
2C$280.C.C2.C2.C$281.C4.2C4$342.A$341.A.A$341.A2.A$342.2A5$339.2A$
339.A.A$335.2A3.A.A$334.A.A4.A$335.A21$321.C$320.C.C3.2C$320.C.C2.C2.
C$321.C4.2C4$382.A$381.A.A$381.A2.A$382.2A5$379.2A$379.A.A$375.2A3.A.
A$374.A.A4.A$375.A14$358.C$357.C.C$358.2C3$362.2C$361.C2.C$362.2C220$
619.3A$619.A$620.A!
EDIT2 Signal reflector with self destruct

Code: Select all

x = 306, y = 493, rule = LifeHistory
249.A$248.A.A$249.2A6$252.2A$252.2A31$249.A$248.A.A$249.2A6$252.2A$
252.2A31$249.A$248.A.A$249.2A6$252.2A$252.2A31$249.A$248.A.A$249.2A6$
252.2A$252.2A31$249.A$248.A.A$249.2A6$252.2A$252.2A31$249.A$248.A.A$
249.2A6$252.2A$252.2A16$2A$2A$303.A$303.A.A$303.2A6$14.A$13.A.A$13.2A
3$11.2A236.A$11.A.A234.A.A$4.2A6.A.A234.2A$3.A2.A6.A$4.A.A$5.A3$252.
2A$252.2A6$34.A$33.A.A$33.2A3$31.2A$31.A.A$24.2A6.A.A$23.A2.A6.A$24.A
.A$25.A10$54.A$53.A.A$53.2A3$51.2A196.A$51.A.A194.A.A$44.2A6.A.A194.
2A$43.A2.A6.A$44.A.A$45.A3$252.2A$252.2A6$74.A$73.A.A$73.2A3$71.2A$
71.A.A$64.2A6.A.A$63.A2.A6.A$64.A.A$65.A10$94.A$93.A.A$93.2A3$91.2A
156.A$91.A.A154.A.A$84.2A6.A.A154.2A$83.A2.A6.A$84.A.A$85.A3$252.2A$
252.2A6$114.A$113.A.A$113.2A3$111.2A$111.A.A$104.2A6.A.A$103.A2.A6.A$
104.A.A$105.A10$134.A$133.A.A$133.2A3$131.2A116.A$131.A.A114.A.A$124.
2A6.A.A114.2A$123.A2.A6.A$124.A.A$125.A3$252.2A$252.2A6$154.A$153.A.A
$153.2A3$151.2A$151.A.A$144.2A6.A.A$143.A2.A6.A$144.A.A$145.A10$174.A
$173.A.A$173.2A3$171.2A76.A$171.A.A74.A.A$164.2A6.A.A74.2A$163.A2.A6.
A$164.A.A$165.A3$252.2A$252.2A6$194.A$193.A.A$193.2A3$191.2A$191.A.A$
184.2A6.A.A$183.A2.A6.A$184.A.A$185.A10$214.A$213.A.A$213.2A3$211.2A$
211.A.A$204.2A6.A.A$203.A2.A6.A$204.A.A$205.A45$266.2A$266.A.A$266.A!

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: The Turing machine

Post by simsim314 » September 16th, 2017, 12:24 pm

Here is how we can convert glider lane -> Eater on corresponding lane

Code: Select all

x = 361, y = 349, rule = LifeHistory
11.C$12.C$10.3C48$156.C$155.C.C$156.2C20$134.2C$133.C2.C$134.C.C$129.
2C4.C$128.C.C$127.C.C$128.C34$159.2C$158.C.C$159.C18$179.2C$146.C31.C
.C$140.C4.C.C31.C$139.C.C3.2C$140.C.C$141.2C5$138.2C$137.C2.C$138.C.C
$139.C7$199.2C$166.C31.C.C$160.C4.C.C31.C$159.C.C3.2C$160.C.C$161.2C
5$158.2C$157.C2.C$158.C.C$159.C7$219.2C$186.C31.C.C$180.C4.C.C31.C$
179.C.C3.2C$180.C.C$181.2C5$178.2C$177.C2.C$178.C.C$179.C7$239.2C$
206.C31.C.C$200.C4.C.C31.C$199.C.C3.2C$200.C.C$201.2C5$198.2C$197.C2.
C$198.C.C$199.C3$3C$2.C$.C2$259.2C$226.C31.C.C$220.C4.C.C31.C$219.C.C
3.2C$220.C.C$221.2C5$218.2C$217.C2.C$218.C.C$219.C7$279.2C$246.C31.C.
C$240.C4.C.C31.C$239.C.C3.2C$240.C.C$241.2C5$238.2C$237.C2.C$238.C.C$
239.C7$299.2C$266.C31.C.C$260.C4.C.C31.C$259.C.C3.2C$260.C.C$261.2C5$
258.2C$257.C2.C$258.C.C$259.C$221.2C$220.C.C$222.C4$319.2C$286.C31.C.
C$280.C4.C.C31.C$279.C.C3.2C$280.C.C$281.2C5$278.2C$277.C2.C$278.C.C$
279.C7$339.2C$306.C31.C.C$300.C4.C.C31.C$299.C.C3.2C$300.C.C$301.2C5$
298.2C$297.C2.C$298.C.C$299.C7$359.2C$326.C31.C.C$320.C4.C.C31.C$319.
C.C3.2C$320.C.C$321.2C5$318.2C$317.C2.C$318.C.C$319.C8$346.C$340.C4.C
.C$339.C.C3.2C$340.C.C$341.2C5$338.2C$337.C2.C$338.C.C$339.C2$356.2C$
356.2C!
Here is a way to create an array of eaters:

Code: Select all

x = 1893, y = 1925, rule = LifeHistory
137$974.A$973.A.A$973.2A357$609.A$608.A.A$607.A2.A6.A$608.2A6.A.A$
615.A.A$615.2A3$617.2A$617.A.A$618.A6$636.C$635.C.C$635.2C2$589.A$
588.A.A$587.A2.A6.A$588.2A6.A.A$595.A.A$595.2A3$597.2A$597.A.A$598.A
10$569.A$568.A.A$567.A2.A6.A$568.2A6.A.A$575.A.A$575.2A3$577.2A$577.A
.A$578.A6$636.C$635.C.C$635.2C2$549.A$548.A.A$547.A2.A6.A$548.2A6.A.A
$555.A.A$555.2A3$557.2A$557.A.A$558.A10$529.A$528.A.A$527.A2.A6.A$
485.A42.2A6.A.A$486.A48.A.A$484.3A48.2A3$537.2A$537.A.A$538.A6$636.C$
635.C.C$635.2C2$509.A$508.A.A$507.A2.A6.A$508.2A6.A.A$515.A.A$515.2A
3$517.2A$517.A.A$518.A10$489.A$488.A.A$487.A2.A6.A$488.2A6.A.A$495.A.
A$495.2A3$497.2A$497.A.A$498.A6$636.C$635.C.C$635.2C2$469.A$468.A.A$
467.A2.A6.A$468.2A6.A.A$475.A.A$475.2A3$477.2A$477.A.A$478.A10$449.A$
448.A.A$447.A2.A6.A$448.2A6.A.A$455.A.A$455.2A3$457.2A$457.A.A$458.A
6$636.C$635.C.C$635.2C2$429.A$428.A.A$427.A2.A6.A$428.2A6.A.A$435.A.A
$435.2A3$437.2A$437.A.A$438.A10$409.A$408.A.A$407.A2.A6.A$408.2A6.A.A
$415.A.A$415.2A3$417.2A$417.A.A$418.A6$636.C$635.C.C$635.2C$404.2A$
404.2A36$636.C$635.C.C$635.2C38$636.C$635.C.C$635.2C38$636.C$635.C.C
1031.2A$635.2C1031.A2.A$1668.A.A$1669.A4.2A$1674.A.A$1675.A.A$1676.A
24$1696.3A$1696.A$1697.A7$636.C$635.C.C$635.2C38$636.C$635.C.C$635.2C
103$635.2C$635.C.C$636.C38$635.2C$635.C.C$636.C38$635.2C$635.C.C$636.
C38$635.2C$635.C.C$636.C38$635.2C$635.C.C$636.C36$404.2A$404.2A$635.
2C$635.C.C$636.C6$418.A$417.A.A$417.2A3$415.2A$415.A.A$408.2A6.A.A$
407.A2.A6.A$408.A.A$409.A10$438.A$437.A.A$437.2A3$435.2A$435.A.A$428.
2A6.A.A$427.A2.A6.A$428.A.A$429.A2$635.2C$635.C.C$636.C6$458.A$457.A.
A$457.2A3$455.2A$455.A.A$448.2A6.A.A$447.A2.A6.A$448.A.A$449.A10$478.
A$477.A.A$477.2A3$475.2A$475.A.A$468.2A6.A.A$467.A2.A6.A$468.A.A$469.
A2$635.2C$635.C.C$636.C6$498.A$497.A.A$497.2A3$495.2A$495.A.A$488.2A
6.A.A$487.A2.A6.A$488.A.A$489.A10$518.A$517.A.A$517.2A3$515.2A$515.A.
A$508.2A6.A.A$507.A2.A6.A$508.A.A$509.A2$635.2C$635.C.C$636.C6$538.A$
537.A.A$537.2A3$484.3A48.2A$486.A48.A.A$485.A42.2A6.A.A$527.A2.A6.A$
528.A.A$529.A10$558.A$557.A.A$557.2A3$555.2A$555.A.A$548.2A6.A.A$547.
A2.A6.A$548.A.A$549.A2$635.2C$635.C.C$636.C6$578.A$577.A.A$577.2A3$
575.2A$575.A.A$568.2A6.A.A$567.A2.A6.A$568.A.A$569.A10$598.A$597.A.A$
597.2A3$595.2A$595.A.A$588.2A6.A.A$587.A2.A6.A$588.A.A$589.A2$635.2C$
635.C.C$636.C6$618.A$617.A.A$617.2A3$615.2A$615.A.A$608.2A6.A.A$607.A
2.A6.A$608.A.A$609.A233$849.2C$849.C.C$850.C!

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: The Turing machine

Post by simsim314 » September 21st, 2017, 7:27 am

Somewhat more accurate splitters and reflectors.

My signal consist of two gliders: self destruct trigger + signal glider. The self destruct is always located to the left, and the lane separation between the two gliders is coding the type of the signal.

Here is a splitter and reflector that preserves the lane separation between the two gliders:

Code: Select all

x = 1905, y = 1033, rule = LifeHistory
284$1626.2A$1626.2A17$1605.2C$1604.C.C$1603.C.C3.2C$1604.C4.C.C$1610.
C2$1006.2C$1005.C.C$1004.C.C3.2C$1005.C4.C.C$1011.C8$1626.C$1625.C.C$
1585.2C38.2C$1584.C.C$1583.C.C3.2C27.2C$1584.C4.C.C26.2C$1590.C2$986.
2C$985.C.C$984.C.C3.2C$985.C4.C.C$991.C10$1565.2C$1564.C.C$1563.C.C3.
2C$1564.C4.C.C$1570.C2$966.2C$965.C.C$964.C.C3.2C$965.C4.C.C$971.C8$
1626.C$1625.C.C$1545.2C78.2C$1544.C.C$1543.C.C3.2C67.2C$1544.C4.C.C
66.2C$1550.C2$946.2C$945.C.C$944.C.C3.2C$945.C4.C.C$951.C10$1525.2C$
1524.C.C$1523.C.C3.2C$1524.C4.C.C$1530.C2$926.2C$925.C.C$924.C.C3.2C$
925.C4.C.C$931.C8$1626.C$1625.C.C$1505.2C118.2C$1504.C.C$1503.C.C3.2C
107.2C$1504.C4.C.C106.2C$1510.C2$906.2C$905.C.C$904.C.C3.2C$905.C4.C.
C$911.C10$1485.2C$1484.C.C$1483.C.C3.2C$1484.C4.C.C$1490.C2$886.2C$
885.C.C$884.C.C3.2C$885.C4.C.C$891.C8$1626.C$1625.C.C$1465.2C158.2C$
1464.C.C$1463.C.C3.2C147.2C$1464.C4.C.C146.2C$1470.C2$866.2C$865.C.C$
864.C.C3.2C$865.C4.C.C$871.C16$846.2C$845.C.C$844.C.C3.2C$845.C4.C.C$
851.C3$1428.2C$1427.C.C$1428.C3$1626.C$1625.C.C$856.2C38.2C38.2C38.2C
38.2C38.2C38.2C38.2C38.2C447.2C$856.2C38.2C38.2C38.2C38.2C38.2C38.2C
38.2C38.2C$1618.2C$1618.2C4$206.C67.C39.C39.C39.C39.C39.C39.C306.2C
30.2C38.2C38.2C38.2C38.2C38.2C38.2C38.2C38.2C$205.C.C65.C.C37.C.C37.C
.C37.C.C37.C.C37.C.C37.C.C304.C.C29.C.C37.C.C37.C.C37.C.C37.C.C37.C.C
37.C.C37.C.C37.C.C$205.2C66.2C38.2C38.2C38.2C38.2C38.2C38.2C306.C31.C
39.C39.C39.C39.C39.C39.C39.C39.C3$203.2C66.2C38.2C38.2C38.2C38.2C38.
2C38.2C$203.C.C65.C.C37.C.C37.C.C37.C.C37.C.C37.C.C37.C.C$204.C.C65.C
.C37.C.C37.C.C37.C.C37.C.C37.C.C37.C.C$205.C67.C39.C39.C39.C39.C39.C
39.C5$274.2C38.2C38.2C38.2C38.2C38.2C38.2C$274.2C38.2C38.2C38.2C38.2C
38.2C38.2C17$1626.C$1625.C.C$1625.2C2$241.C1376.2C$240.C.C1375.2C$
240.2C3$238.2C$238.C.C$239.C.C$240.C10$1147.2C$1147.C.C$261.C885.C$
260.C.C$260.2C3$258.2C$258.C.C$259.C.C$260.C8$1626.C$1625.C.C$1625.2C
2$281.C144.2C1190.2C$280.C.C143.C.C1189.2C$280.2C144.C3$278.2C$278.C.
C$279.C.C$280.C3$1678.3C$1678.C$1679.C7$301.C$300.C.C$300.2C3$298.2C$
298.C.C$299.C.C$300.C8$1626.C$1625.C.C$1625.2C2$321.C1296.2C$320.C.C
1295.2C$320.2C3$318.2C$318.C.C$319.C.C$320.C12$341.C$340.C.C$340.2C3$
338.2C$338.C.C$339.C.C$340.C12$361.C$360.C.C$360.2C3$358.2C$358.C.C$
359.C.C$360.C18$1628.2C$1628.C.C$1624.2C3.C.C$1623.C.C4.C$1624.C41$
1047.3C$1047.C$1048.C2$433.2C$433.C.C$433.C48$1722.3C$1722.C$1723.C!

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: The Turing machine

Post by simsim314 » September 22nd, 2017, 6:42 am

Here is SL reader, that will convert SL lane into signal, but when no SL is present, it will still output signal lane, thus the turing machine can expect empty space - or infinite not filled grid as an input tape:

Code: Select all

x = 649, y = 697, rule = LifeHistory
600.C$599.C.C$599.2C6$647.2A$647.2A11$580.C$579.C.C$579.2C48.C$628.C.
C$629.2C3$631.2C$630.C.C$629.C.C$630.C10$560.C$559.C.C$559.2C48.C$
608.C.C$609.2C3$611.2C$610.C.C$609.C.C$610.C10$540.C$539.C.C$539.2C
48.C$588.C.C$589.2C3$591.2C$590.C.C$589.C.C$590.C10$520.C$519.C.C$
519.2C48.C$568.C.C$569.2C3$571.2C$570.C.C$569.C.C$570.C10$500.C$499.C
.C$499.2C48.C$548.C.C$549.2C3$551.2C$550.C.C$549.C.C$550.C10$480.C$
479.C.C$479.2C48.C$528.C.C$529.2C3$531.2C$530.C.C$529.C.C$530.C10$
460.C$459.C.C$459.2C48.C$508.C.C$509.2C3$511.2C$510.C.C$509.C.C$510.C
10$440.C$439.C.C$439.2C48.C$488.C.C$489.2C3$491.2C$490.C.C$489.C.C$
490.C10$420.C$419.C.C$419.2C48.C$468.C.C$469.2C3$471.2C$470.C.C$469.C
.C$470.C12$404.2C43.C$404.2C42.C.C$449.2C3$451.2C$450.C.C$407.2C40.C.
C$407.C.C40.C$408.C11$384.2C43.C$384.2C42.C.C$429.2C3$431.2C$430.C.C$
387.2C40.C.C6.2C$387.C.C40.C6.C2.C$388.C48.C.C$438.C10$364.2C43.C$
364.2C42.C.C$409.2C3$411.2C$410.C.C$367.2C40.C.C6.2C$367.C.C40.C6.C2.
C$368.C48.C.C$418.C10$344.2C43.C$344.2C42.C.C$389.2C3$391.2C$390.C.C$
347.2C40.C.C6.2C$347.C.C40.C6.C2.C$348.C48.C.C$398.C10$324.2C43.C$
324.2C42.C.C$369.2C3$371.2C$370.C.C$327.2C40.C.C6.2C$327.C.C40.C6.C2.
C$328.C48.C.C$378.C118.2A$497.2A9$304.2C43.C136.C$304.2C42.C.C134.C.C
$349.2C135.2C3$351.2C135.2C$350.C.C134.C.C$307.2C40.C.C6.2C126.C.C6.
2C$307.C.C40.C6.C2.C126.C6.C2.C$308.C48.C.C134.C.C$358.C136.C10$284.
2C43.C136.C$284.2C42.C.C134.C.C$329.2C135.2C3$331.2C135.2C$330.C.C
134.C.C$287.2C40.C.C6.2C126.C.C6.2C$287.C.C40.C6.C2.C126.C6.C2.C$288.
C48.C.C134.C.C$338.C136.C10$264.2C43.C136.C$264.2C42.C.C134.C.C$309.
2C135.2C3$311.2C135.2C$310.C.C134.C.C$267.2C40.C.C6.2C126.C.C6.2C$
267.C.C40.C6.C2.C126.C6.C2.C$268.C48.C.C134.C.C$318.C136.C10$244.2C
43.C136.C$244.2C42.C.C134.C.C$289.2C135.2C3$291.2C135.2C$290.C.C134.C
.C$247.2C40.C.C6.2C126.C.C6.2C$247.C.C40.C6.C2.C126.C6.C2.C$248.C48.C
.C134.C.C$298.C136.C10$224.2C43.C136.C$224.2C42.C.C134.C.C$269.2C135.
2C3$271.2C135.2C$270.C.C134.C.C$227.2C40.C.C6.2C126.C.C6.2C$227.C.C
40.C6.C2.C126.C6.C2.C$228.C48.C.C134.C.C$278.C136.C10$249.C136.C$248.
C.C134.C.C$249.2C135.2C3$251.2C135.2C$250.C.C134.C.C$249.C.C6.2C126.C
.C6.2C$250.C6.C2.C126.C6.C2.C$257.C.C134.C.C$258.C136.C10$366.C$365.C
.C$366.2C3$368.2C$367.C.C$366.C.C6.2C$367.C6.C2.C$245.2C127.C.C$245.C
.C127.C$246.C368.2A$615.2A8$346.C$345.C.C256.C$346.2C255.C.C$604.2C2$
348.2C$347.C.C256.2C$346.C.C6.2C248.C.C$347.C6.C2.C246.C.C$354.C.C
248.C$355.C4$255.C$254.C.C$254.2C4$326.C$325.C.C256.C$326.2C255.C.C$
584.2C2$328.2C$327.C.C256.2C$326.C.C6.2C248.C.C$327.C6.C2.C246.C.C$
334.C.C248.C$335.C5$168.2C$167.C.C$168.CB4$287.C187.2A87.C$286.C.C
186.2A86.C.C$286.C.C275.2C$287.C2$566.2C$565.C.C$564.C.C$565.C2$286.
2C$285.C.C$284.C.C$285.C7$544.C$543.C.C$544.2C3$546.2C$545.C.C$544.C.
C$545.C7$190.2C$189.C2.C6.2C$190.2C7.C.C$200.C.C$201.C$524.C$523.C.C$
524.2C3$526.2C$525.C.C$524.C.C$525.C4$72.2C$71.C.C$72.C6$504.C$503.C.
C$504.2C3$506.2C$505.C.C$504.C.C$505.C12$484.C$483.C.C$484.2C3$486.2C
$485.C.C$484.C.C$485.C12$464.C$463.C.C$233.3B228.2C3$466.2C$465.C.C$
464.C.C$121.C343.C$120.C.C4.C$121.2C3.C.C$125.C.C$125.2C28$424.C$423.
C.C$424.2C3$426.2C$425.C.C$424.C.C$425.C35$.2C$C.C$.C379.2C$380.C.C$
382.C24$21.2C$21.C.C$22.C!
Last edited by simsim314 on September 22nd, 2017, 8:38 am, edited 1 time in total.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: The Turing machine

Post by dvgrn » September 22nd, 2017, 7:32 am

simsim314 wrote:Here is SL reader, that will convert SL lane into signal, but when no SL is present, it will still output signal lane, thus the turing machine can expect empty space - or infinite not filled grid as an input tape...
Are you at the stage yet where you can draw up a rough blueprint? E.g., do you have an idea how many blocked-off gun loops there will need to be?

Should the blocking and unblocking of guns be done by building and destroying eaters, maybe along the same lines as in a universal regulator? Or is there a simpler kind of ON/OFF switch? Come to think of it, are there any Herschel-based permanent switches that work with signals 90 ticks apart? The old ones include an F116 or F166 conduit, and those are too slow:

Code: Select all

#C Herschel latch pattern, too slow for single-channel
#C   due to F116 conduit needed to extract the output signal.
#C Herschel pulse entering at [1] {nondestructive READ} will pass
#C   through to [3] {OUTPUT} if no block is present {Latch is SET}.
#C   Herschel pulse entering at [2] {CLEAR} will create the block.
#C   Glider entering at [4] {SET} will destroy the block if present; if
#C   not, glider passes through and is eatered by a tub-with-tail.
x = 131, y = 145, rule = LifeHistory:P820,740
12$43.2A3.2A$43.2A3.2A2$43.2A3.2A$43.A.A.A.A$45.A.A$44.2A.A$48.2A$49.
A$48.A$48.2A$41.BD6.A$24.2A15.2BD4.A$24.A16.3DB3.2A$25.A16.4B14.A$24.
2A17.4B4.2A5.3A$44.4B4.A4.A$24.2A19.4B3.A.AB2.A38.2A.A$24.A21.4B3.A.A
3BA37.A.2A$25.A21.4B3.A3B2A41.2A$11.2A11.2A22.4B.3B.B43.A$12.A36.6B6.
A9.A30.A$12.A.AB8.2A17.A6.6B5.3A5.3A29.2A$13.2AB8.A18.3A4.7B7.A3.A28.
2A.A$15.3B7.A20.A.10B5.2A.B.2A27.A.2A$15.4B5.2A19.A.A4B.6B4.7B31.2A$
16.4B25.BA2B.10B3.5B7.2A7.2A15.A$12.B4.4B19.A5.2B3.10B2.6B5.B2A2B5.A.
A15.A$12.5B.4B16.3A6.2B3.17B6.4B2.BA.A.3A12.2A$12.17B8.A8.B2AB3.16B4.
7B.B2A5.A7.2A.A$12.13BD4B7.2A8.2A5.16B2.11B5.2A7.A.2A$12.11B3D4B2.B.
5B16.15B3.9B6.4B$12.11BDBD4B.6B19.16B.12B5.3B$12.11BD13B7.7B.B4.15B.
16B.4B$12.B3.2B2.19B.B3.13B.43B$23.49B.24BD4B$25.70B3D4B$26.43B2C24BD
BD4B$25.21B2A13B3.5B2C24BD6B$25.7B.13B2A14B.22B3.2B2.10B$23.2AB.3B4.
6B2.11B3.2B2.2B3.17B12.8B$22.A.AB9.4B3.10B8.17B$22.A10.5B5.6B10.18B$
21.2A10.2A9.3B11.19B$34.A9.B5.2A5.21B$31.3A9.2A4.B2AB3.23B$31.A11.A6.
2B3.4B.12B.7B$44.A4.2B3.4B.13B.8B$43.2A3.BA2B.4B2.6B2.4B4.7B$48.A.A5B
3.6B4.B3.10B$49.A.4B4.6B8.2A3.6B$46.3A4.B4.8B8.A4.6B$46.A12.8B4.3A6.
6B$58.9B4.A5.B3.6B$58.9B9.2AB.3B.4B$58.10B8.2A3BA3.4B$58.5B2A3B9.B.BA
.A3.4B$58.5B2A4B11.BA.A3.4B$58.11B14.A4.4B$58.4B.7BA.2A9.2A4.4B$60.B
3.4B2.2A.A16.4B$61.2B2.2B24.4B$60.6B26.4B$52.2A5.7B27.4B$53.A6.7B27.
4B$53.A.AB2.8B28.4B$54.2AB2.9B28.4B$56.12B29.4B$56.12B30.4B$56.10B.B
2A29.4B$57.8B2.BA.A29.4B$56.8B6.A30.4B$57.8B5.2A30.4B$58.7B38.4B$55.
11B38.4B$54.12B39.4B$45.2A7.12B40.4B$44.A2.A2.2A2.11B42.4B$45.2A2.A.A
2.B3.4B.4B41.4B10.2A$47.2A.B3.2B.4B4.2A42.4B9.A$47.A2.2B2.2B3.2B4.A
44.4B10.A$44.2A.A.BA2B.6B6.3A35.2A5.6B3.5A$44.A.2A.A.A8B8.A36.A5.6B2.
A$48.A.A.8B45.A.AB.7B2.B3A$45.2A2.A4.5B47.2AB.7B3.2B.A$43.3A.2A4.6B
49.12B4A$42.A4.B6.6B48.7B2A3BAB2.2A$43.3AB2AB3.7B48.7B2A2B.B3A2.A$45.
A.2AB.8B49.10B3.B.A.2A$49.10B30.2A16.8B8.A$49.6B2A3B28.B2AB14.9B7.2A$
49.6B2A2B5.2A16.B6.2B14.4B2.3B$49.10B5.A2.A13.3B4.2B14.4B3.5B$48.11B
2.BA.A.2A9.14B12.4B7.2A$48.12B.B2A.A11.14B11.4B8.A$47.15B3.A10.18B5.B
.4B10.3A$46.16B3.3A7.29B13.A$43.2B.16B6.A5.30B$42.2A18B5.2A4.31B$42.
2AB.17B4.37B$43.B.4B.8B2.4B5.34B$50.7B4.4B2.8B2.23B2.B2A$51.6B5.15B3.
16B.B4.BA.A$53.4B6.14B4.2B.10B11.A$55.3BA5.13B7.9B12.2A$56.BA.A5.10B.
B2A6.11B$57.A.A5.5B2AB3.BA.A5.12B$58.A6.5B2AB6.A5.12B$59.3A7.4B6.2A5.
11B$61.A7.3B12.4B.4B3DB$66.AB.2B13.2A4.4BD2B$65.A.AB2AB13.A4.2B3D2B$
65.A.ABABAB9.3A6.6B$62.2A.A.A.A.A2.A7.A8.7B$62.A2.A2.2A.4A18.B.4B$64.
2A4.A25.4B$70.A.A24.3B$71.2A25.2B2A$99.BA.A$78.2A.A20.A$78.A.2A20.2A$
82.2A$82.A$83.A$82.2A$78.2A.A$78.A.2A$76.2A$76.A$77.A$76.2A$78.2A.A$
78.A.2A!

Code: Select all

#C F166-based switch:
#C A Herschel at [1] passes through to [5]
#C   unless a CLOSE glider pulse is sent in at [3].
#C   The [3] glider moves a block to a point that
#C   allows it to consume all following Herschels [2]
#C   unless an OPEN glider pulse is sent in at [4]
#C   to move the block back to its original position.
x = 166, y = 100, rule = LifeHistory:P820,740
135.2A.A$135.A.2A$139.2A$139.A$140.A$139.2A$135.2A.A$135.A.2A10.AB$
139.2A7.AB.B$139.A8.3A$140.A$8.2A.A127.2A$8.A.2A45.2A76.2A.A$12.2A44.
A76.A.2A$12.A44.A$13.A43.2A$12.2A$8.2A.A45.2A$8.A.2A46.A$6.2A49.A$6.A
50.2A$7.A$6.2A49.2A$8.2A.A46.A$8.A.2A28.2A15.A$41.A15.2A$41.A.AB$42.
2AB$44.3B$44.4B$31.2A12.4B14.A9.A$6.2A24.A13.4B13.3A5.3A45.3B$7.A13.
2A6.3A15.4B15.A3.A13.2A33.5B$7.A.AB9.B2A2B4.A18.4B13.2A.B.2A13.A32.6B
$8.2AB.3B6.4B.3B20.4B12.7B12.A33.8B$10.7B2.11B7.7B6.4B13.3B14.2A32.8B
7.2A$10.22B.B3.7B7.4B11.6B13.B26.B4.9B8.A$11.51B4.6B2.2B9.3B19.7B3.
11B5.A$10.48BA4B2.7B.4B7.6B16.9B2.13B3.2A$8.48B3A4B2.16B2.10B10.13B.
13B4.B$6.33B2A15BABA4B.30B3.2B2.28B5.3B19.4B4.A$6.2BA30B2A15BA30B2A
41B3.6B16.5B3.A.A$5.3BABA4B.30B3.2B2.34B2A41B2.10B11.7B3.A.A$6.2B3A4B
2.16B2.10B10.53B2A21B.11B3.2B2.10B4.A$5.5BA4B2.7B.4B7.6B16.50B2A26B2A
15BD6B$4.10B4.6B2.2B9.3B19.77B2A15BDBD4B$3.4B11.6B13.B20.22B.B3.13B.B
2.B2.48B3D4B$19.3B14.2A20.7B2.11B7.7B.B13.B2.45BD4B$2.2A13.7B12.A19.
2AB.3B6.4B.3B32.50B$3.A13.2A.B.2A13.A17.A.AB9.B2A2B4.A30.24B2.13B.4B$
3A15.A3.A13.2A17.A13.2A6.3A27.25B2.7B.B4.4B$A14.3A5.3A28.2A24.A25.4B.
20B15.4B$15.A9.A53.2A24.4B2.18B16.4B$104.4B4.18B.B12.4B$103.4B6.18B2A
10.4B$102.4B7.18B2A9.4B$101.4B8.3B3.13B9.4B$100.4B10.B2.3B.11B8.4B$
100.3B14.2A2.9B10.3B11.A.2A$98.2A2B16.A3.7B9.2AB13.2A.A$97.A.AB14.3A
5.4B10.A.AB11.2A$97.A17.A8.5B8.A15.A$96.2A29.2A7.2A14.A$127.A24.2A$
128.3A23.A.2A$130.A23.2A.A$158.2A$159.A$158.A$158.2A$154.A.2A$154.2A.
A15$68.2A3.2A$68.2A3.2A2$57.3A8.2A3.2A$58.BA8.A.A.A.A$58.A11.A.A$69.
2A.A$73.2A$74.A$73.A$73.2A$74.A$73.A$73.2A!
I must be forgetting some modern small switchable circuit -- hopefully not one that I built myself last month. (?)

EDIT:It might be possible to make something out of this, I suppose -- at least that was a couple of years ago, so it seems okay if the memory has faded a bit.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: The Turing machine

Post by simsim314 » September 22nd, 2017, 8:02 am

dvgrn wrote:Are you at the stage yet where you can draw up a rough blueprint? E.g., do you have an idea how many blocked-off gun loops there will need to be?
Well more or less. I know all the components - and I have a mock script that I'll need to fill with real code, but the basic functions are there - and there are not so many of them (it's turing machine you know - it supposed to be minimalistic).

Here is my mock code:

Code: Select all

import golly as g

def place_splitter(num_states, signal): 
	signal1 = None
	signal2 = None
	return (signal1, signal2)
	
def place_SL_reader(num_states):	
	
	signal = None
	return signal

def place_rule_SL_writer(num_states, signal, rule_table):
	signal = None
	return signal

def place_rule_left(num_states, signal, rule_table):
	signal = None
	return signal
	
def place_rule_right(num_states, signal1, rule_table):
	signal = None
	return signal
	
def place_rule(num_states, signal, rule_table):
	
	singal1, signal2 = place_splitter(num_states, signal)
	singal1, signal3 = place_splitter(num_states, signal1)
	
	signal1 = place_rule_SL_writer(num_states, signal1)
	signal2 = place_rule_left(num_states, signal2)
	signal3 = place_rule_right(num_states, signal3)
	
	return (signal_SL, signal_left, signal_right)
	
def place_SL(num_states, signal):
	pass

def place_left_activator(num_states, signal):
	pass

def place_right_activator(num_states, signal):
	pass
	
def place_all(num_states, rule_table):
	signal = place_SL_reader(num_states)
	signal_SL, signal_left, signal_right = place_rule(num_states, signal, rule_table)
	place_SL(num_states, signal_SL)
	place_left_activator(num_states, signal_left)
	place_right_activator(num_states, signal_right)
	
I think somewhere around 15-20 of those self destruct arrays.

I want to make it general - so it would be possible to "compile" any turing machine table into my turing machine model.

Basically each "head" state has its own gun to generate the rule table for the corresponding head state - additionally I have some gun that works always and is capable to place SLs in front of the eaters that block the rule table part.
dvgrn wrote:Should the blocking and unblocking of guns be done by building and destroying eaters
I'm blocking with eaters array. I've posted the design here.

Post Reply