does there exists a 60 degree pseudo spaceship?
does there exists a 60 degree pseudo spaceship?
Does there exists a pattern P, such that if the n-th generation (in rule B3/S23) of P is P_n, then P_n is not empty, and every cell in P_n has coordinate (vn+o(n),sqrt(3)vn+o(n)) for some speed v?
Further more, could o(n) be changed to O(sqrt(log(n)))?
Further more, could o(n) be changed to O(sqrt(log(n)))?
Re: does there exists a 60 degree pseudo spaceship?
It's certainly theoretically possible to make a Universal Constructor that copies itself either east or south, deciding based on a binary counter recording how many times it's been copied. We want the ratio of times that it moves east to the number of times it moves south to tend to 1:sqrt(3).
Unfortunately, the time taken to decide whether to move east or south must tend to infinity with n, which makes the timing calculations rather tricky. Also the space needed to do this calculation will also tend to infinity, so I'm not sure if we can stay inside the O(sqrt(log(n))) box.
Unfortunately, the time taken to decide whether to move east or south must tend to infinity with n, which makes the timing calculations rather tricky. Also the space needed to do this calculation will also tend to infinity, so I'm not sure if we can stay inside the O(sqrt(log(n))) box.
- BlinkerSpawn
- Posts: 1992
- Joined: November 8th, 2014, 8:48 pm
- Location: Getting a snacker from R-Bee's
Re: does there exists a 60 degree pseudo spaceship?
Since only the counter would have to change between iterations, it should be possible to stay within sqrt(log(n)), since that's the space a rectangularly-packed binary counter requires. Of course, this requires that n -> n*sqrt(3) can be calculated with constant space (time being irrelevant in this regard).Macbi wrote:Unfortunately, the time taken to decide whether to move east or south must tend to infinity with n, which makes the timing calculations rather tricky. Also the space needed to do this calculation will also tend to infinity, so I'm not sure if we can stay inside the O(sqrt(log(n))) box.
Re: does there exists a 60 degree pseudo spaceship?
It can't, you need at least O(log(n)) space to even store the answer. Probably more than that to do the calculation.BlinkerSpawn wrote:Of course, this requires that n -> n*sqrt(3) can be calculated with constant space
If the ship has a constant time-per-generation I don't see how it can work once the time for calculation becomes bigger than that.(time being irrelevant in this regard).
This thread could be useful.
Re: does there exists a 60 degree pseudo spaceship?
If you need at least O(log(n)) space to even store the answer, then your construction can not solve the question.Macbi wrote:It can't, you need at least O(log(n)) space to even store the answer. Probably more than that to do the calculation.BlinkerSpawn wrote:Of course, this requires that n -> n*sqrt(3) can be calculated with constant spaceIf the ship has a constant time-per-generation I don't see how it can work once the time for calculation becomes bigger than that.(time being irrelevant in this regard).
This thread could be useful.
Is there other way to solve it.
Re: does there exists a 60 degree pseudo spaceship?
If the calculation needed exactly O(log(n)) space then we would be okay, since we have that much space within a O(sqrt(log(n))) bounding box. But if we need any more space then we would be stuck.5772156 wrote:If you need at least O(log(n)) space to even store the answer, then your construction can not solve the question.Macbi wrote:It can't, you need at least O(log(n)) space to even store the answer. Probably more than that to do the calculationBlinkerSpawn wrote:Of course, this requires that n -> n*sqrt(3) can be calculated with constant space
Is there other way to solve it.
If we stored the number of times moved east and the number of times moved south then we would just need to compute whether or not we had E^2 < 3S^2, which would allow us to work only with integers and avoid having to calculate sqrt(3). But it still leaves the question of whether we can calculate n^2 in space O(log(n)).
Re: does there exists a 60 degree pseudo spaceship?
Great idea! That's very elegant.Macbi wrote:If we stored the number of times moved east and the number of times moved south then we would just need to compute whether or not we had E^2 < 3S^2, which would allow us to work only with integers and avoid having to calculate sqrt(3).
Of course -- just take the standard repeated shifting algorithm. O(log(n)) space means you can have a bounded number of registers each of O(log(n)) bits.But it still leaves the question of whether we can calculate n^2 in space O(log(n)).
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: does there exists a 60 degree pseudo spaceship?
Ah, yes. I was thinking that the standard algoritm would take O(log(n)^2) space, because that's what it takes to do long multiplication on paper. But of course on a computer you don't have to write out every intermediate result separately, you can just add them into a running total. So we can do it in O(log(n)) space.calcyman wrote:Of course -- just take the standard repeated shifting algorithm. O(log(n)) space means you can have a bounded number of registers each of O(log(n)) bits.
Now we have to worry about computation time. The ship that translates itself a trillion cells east if E^2 < 3S^2 and a trillion cells south otherwise won't travel at a constant speed. The nth generation will need O(log(n)^2) computation time, and hence its velocity will only be O(1/log(n)^2). Also, the ship will break down when its size exceeds a trillion.
What about a ship that fires loafers east and south before it begins its calculations and then shoots them down with LWSSes once the calculation has finished, deleting one and using the other as a target for the construction of the copy? I think that should travel at a constant speed, but it will take a little bit of thought to make myself absolutely certain of all the details. For example the copying operation itself takes O(log(n)) time. Could that cause a problem?
Last edited by Macbi on March 19th, 2021, 6:15 pm, edited 1 time in total.
Re: does there exists a 60 degree pseudo spaceship?
I think we're okay. We have one or more internal tapes of size O(sqrt(log(n))-by-O(sqrt(log(n)) along similar lines to the 0E0P metacell, and another identical loop which only contains a single glider to act as a 'clock'. The 'clock' tape uses demultiplexers to allow the glider to be advanced or delayed by 256 ticks at will; this has the effect of allowing Turing-machine motion through the information-carrying tape.Macbi wrote:What about a ship that fires loafers east and south before it begins its calculations and then shoots them down with LWSSes once the calculation has finished, deleting one and using the other as a target for the construction of the copy? I think that should travel at a constant speed, but it will take a little bit of thought to makke myself absolutely certain of all the details. For example the copying operation itself takes O(log(n)) time. Could that cause a problem?
Then we can abstract ourselves out of the GoL engineering nightmare and into the problem of engineering a Turing machine to perform the arithmetic and produce the construction. We just need the Turing machine to spend an equal number of cycles between firing its loafers (actually Corderships) and shooting them down, and the daughter machine firing its loafers. That shouldn't be impossible.
What do you do with ill crystallographers? Take them to the mono-clinic!
Re: does there exists a 60 degree pseudo spaceship?
This is an old post, but I realised a better way to do this. We could store E, S and D = E^2-3S^2. Then when we move east we update E = E+1 and D = D+2E+1. When we move south we do S = S+1 and D = D-6S-3. This let's us work out if D is positive or negative without ever having to square E or S.Macbi wrote: ↑November 8th, 2018, 6:05 amIf we stored the number of times moved east and the number of times moved south then we would just need to compute whether or not we had E^2 < 3S^2, which would allow us to work only with integers and avoid having to calculate sqrt(3). But it still leaves the question of whether we can calculate n^2 in space O(log(n)).
Re: does there exists a 60 degree pseudo spaceship?
If we store F=2E instead of E, then we can do three additions instead of three additions and a multiplication.Macbi wrote: ↑June 18th, 2022, 6:03 amThis is an old post, but I realised a better way to do this. We could store E, S and D = E^2-3S^2. Then when we move east we update E = E+1 and D = D+2E+1. When we move south we do S = S+1 and D = D-6S-3. This let's us work out if D is positive or negative without ever having to square E or S.Macbi wrote: ↑November 8th, 2018, 6:05 amIf we stored the number of times moved east and the number of times moved south then we would just need to compute whether or not we had E^2 < 3S^2, which would allow us to work only with integers and avoid having to calculate sqrt(3). But it still leaves the question of whether we can calculate n^2 in space O(log(n)).
F=F+1
D=D+F
F=F+1
T=6S still requires a subtraction
T=T+3
D=D-T
T=T+3
Can we store E^2 and 3S^2 separately and compare them?
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116