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?