Page 1 of 1
The Turing machine
Posted: September 7th, 2017, 11:15 am
by gameoflifemaniac
How to use the (universal) Turing machine in Conway's Game of Life?
Re: The Turing machine
Posted: September 7th, 2017, 12:35 pm
by dvgrn
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...)
Re: The Turing machine
Posted: September 12th, 2017, 2:17 pm
by simsim314
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.
Re: The Turing machine
Posted: September 12th, 2017, 3:33 pm
by dvgrn
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.
Re: The Turing machine
Posted: September 12th, 2017, 5:33 pm
by simsim314
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.
Re: The Turing machine
Posted: September 12th, 2017, 9:31 pm
by dvgrn
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.
Re: The Turing machine
Posted: September 13th, 2017, 3:14 am
by simsim314
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.
Re: The Turing machine
Posted: September 13th, 2017, 6:24 am
by simsim314
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!
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!
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!
Re: The Turing machine
Posted: September 16th, 2017, 12:24 pm
by simsim314
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!
Re: The Turing machine
Posted: September 21st, 2017, 7:27 am
by simsim314
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!
Re: The Turing machine
Posted: September 22nd, 2017, 6:42 am
by simsim314
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!
Re: The Turing machine
Posted: September 22nd, 2017, 7:32 am
by dvgrn
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.
Re: The Turing machine
Posted: September 22nd, 2017, 8:02 am
by simsim314
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.