does there exists a 60 degree pseudo spaceship?

For general discussion about Conway's Game of Life.
Post Reply
5772156
Posts: 2
Joined: May 6th, 2018, 8:15 am

does there exists a 60 degree pseudo spaceship?

Post by 5772156 » November 3rd, 2018, 11:52 pm

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)))?

User avatar
Macbi
Posts: 699
Joined: March 29th, 2009, 4:58 am

Re: does there exists a 60 degree pseudo spaceship?

Post by Macbi » November 4th, 2018, 3:19 pm

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.

User avatar
BlinkerSpawn
Posts: 1905
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: does there exists a 60 degree pseudo spaceship?

Post by BlinkerSpawn » November 4th, 2018, 3:56 pm

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.
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).
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image

User avatar
Macbi
Posts: 699
Joined: March 29th, 2009, 4:58 am

Re: does there exists a 60 degree pseudo spaceship?

Post by Macbi » November 4th, 2018, 4:45 pm

BlinkerSpawn wrote:Of course, this requires that n -> n*sqrt(3) can be calculated with constant space
It can't, you need at least O(log(n)) space to even store the answer. Probably more than that to do the calculation.
(time being irrelevant in this regard).
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.

This thread could be useful.

5772156
Posts: 2
Joined: May 6th, 2018, 8:15 am

Re: does there exists a 60 degree pseudo spaceship?

Post by 5772156 » November 8th, 2018, 4:48 am

Macbi wrote:
BlinkerSpawn wrote:Of course, this requires that n -> n*sqrt(3) can be calculated with constant space
It can't, you need at least O(log(n)) space to even store the answer. Probably more than that to do the calculation.
(time being irrelevant in this regard).
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.

This thread could be useful.
If you need at least O(log(n)) space to even store the answer, then your construction can not solve the question.
Is there other way to solve it.

User avatar
Macbi
Posts: 699
Joined: March 29th, 2009, 4:58 am

Re: does there exists a 60 degree pseudo spaceship?

Post by Macbi » November 8th, 2018, 6:05 am

5772156 wrote:
Macbi wrote:
BlinkerSpawn wrote:Of course, this requires that n -> n*sqrt(3) can be calculated with constant space
It can't, you need at least O(log(n)) space to even store the answer. Probably more than that to do the calculation
If you need at least O(log(n)) space to even store the answer, then your construction can not solve the question.
Is there other way to solve it.
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.

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)).

User avatar
calcyman
Posts: 2095
Joined: June 1st, 2009, 4:32 pm

Re: does there exists a 60 degree pseudo spaceship?

Post by calcyman » November 8th, 2018, 6:27 am

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).
Great idea! That's very elegant.
But it still leaves the question of whether we can calculate n^2 in space O(log(n)).
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.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Macbi
Posts: 699
Joined: March 29th, 2009, 4:58 am

Re: does there exists a 60 degree pseudo spaceship?

Post by Macbi » November 8th, 2018, 7:04 am

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.
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.

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 makke myself absolutely certain of all the details. For example the copying operation itself takes O(log(n)) time. Could that cause a problem?

User avatar
calcyman
Posts: 2095
Joined: June 1st, 2009, 4:32 pm

Re: does there exists a 60 degree pseudo spaceship?

Post by calcyman » November 8th, 2018, 8:05 am

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?
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.

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!

Post Reply