Computer with A Separated Program

[nalA]

(Actually I'm not sure whether this name is suitable for this thread)

Most (programmable) Life computers today seem to hardcode their programs in their circuits by placing several reflectors, duplicators, etc. I'm trying to construct a programmable computer that reads its program from a specific separated space.

The program could be encoded in an array of still-lifes or a glider stream. Reading the program from still-lifes requires the whole computer to move (I don't want to use reading heads because they're very slow when the bit is far away, but it's still a choice), resulting in the computer containing self-constructing mechanisms and thus being extremely large. I prefer glider streams but I don't quite know how to actually implement it.

Any ideas?

[dvgrn]

The program could be encoded in an array of still-lifes or a glider stream. Reading the program from still-lifes requires the whole computer to move (I don't want to use reading heads because they're very slow when the bit is far away, but it's still a choice), resulting in the computer containing self-constructing mechanisms and thus being extremely large. I prefer glider streams but I don't quite know how to actually implement it.

Any ideas?

The idea of building a self-constructing computer has come up at least a couple of times recently. It seems like you've looked into the problem far enough to find the seemingly inevitable awkward trade-offs:

• If your program is stored on a one-dimensional "tape" (line of still lifes), and you want to move a read head to read a faraway bit on the tape,
  • a stationary computer has to wait a long time to get an answer back... but
  • a moving computer has other problems that are much much worse than that, relating retaining program state while repeatedly constructing and destroying a big complex mechanism;
• If your program is stored in a glider loop, you can only read the program at certain times -- you have to wait for the beginning of the program to cycle around so that you can start reading it. So you end up waiting around a lot anyway.

There are at least two possible ways to dodge these problems ... though, not surprisingly, they create other problems that will need to be solved instead:

1) It's possible to build a mechanism that reads a 1-dimensional tape of still lifes non-destructively, in one continuous pass, and returns a stream of gliders immediately. The fact that part of the tape may be far away doesn't matter, because you can only process instructions at a certain rate anyway, and instructions will be coming in one after the other with no long delays at any stage.

2) If you want fast "random access" to a memory area instead of sequential access, you can avoid long delays by building an addressable 2-dimensional memory.

We have 2D memory mechanisms already, in the Osqrtlogt pattern and its various successors (some of which actually use the memory area more as a display than as a binary storage device). But nobody has been ambitious enough yet to build the additional control mechanisms that would allow memory addresses to be stored in the 2D memory, that refer to other locations in that same 2D memory.

-- In fact, the 2D memory unit is one of the few calculating devices that has not yet been re-designed to use much smaller 2020's-era circuitry. Seems like it is such a tricky piece of wiring that nobody dares to touch it! It dates from way back in 2010, before Snarks and syringes and dozens of other discoveries that would allow a much more compact 2D memory to be built.

[nalA]

1) It's possible to build a mechanism that reads a 1-dimensional tape of still lifes non-destructively, in one continuous pass, and returns a stream of gliders immediately. The fact that part of the tape may be far away doesn't matter, because you can only process instructions at a certain rate anyway, and instructions will be coming in one after the other with no long delays at any stage.

This, as well as the glider stream scheme, seems to require the program to be completely sequential. Maybe there are ways to encode some jumping logic into sequential instructions, but extra parsing is needed. Actually continuous reading seems to produce just a glider stream whose timing could be strictly controlled.

2) If you want fast "random access" to a memory area instead of sequential access, you can avoid long delays by building an addressable 2-dimensional memory.

Sorry I don't understand how 2D registers are able to avoid long delays. However I can indeed reformat the still-life tape into a 2D form, like 4 bytes in a row; it could help, but not much.

I start to believe that long delays brought by the stable tape are rather acceptable

[dvgrn]

This, as well as the glider stream scheme, seems to require the program to be completely sequential...

Yup, jumps and subroutines are two more things that are much more awkward to implement with a glider-based storage mechanism. The 0E0P metacell manages this trick without too much trouble, but there are just two subroutines, executed a fixed number of times each -- no programmatic control over which subroutine to jump to next, or anything like that.

Better support for subroutines would be one of the big advantages of a 2D program memory. Each subroutine could easily be stored in its own row in a rectangular memory block. Reading a different subroutine would be just a quick adjustment, bumping one of the two read heads forward or back a few rows, and resetting the other read head to zero.

Or each subroutine could be stored in its own NxN area, instead. For example, we could build a mechanism that quickly adjusts the X and Y read heads to point to a given block, then reads out all of the bits in that block and produces a glider stream to be processed elsewhere.

Other ideas are certainly possible. E.g., there are ways to design memory tapes with an arbitrarily large number of read heads. So even with a single 1D tape, we could invent mechanisms that do things like "Read N bits from the tape starting from the current position of head #H."

You definitely start seeing the same old problem with longer wait times for retrieving faraway subroutines, but honestly HashLife is really good at speeding up the boring parts so that designs like that would still be runnable in Golly.

Sorry I don't understand how 2D registers are able to avoid long delays.

A 2D storage mechanism moves the average distance to the bit that you want from O(L) to O(sqrt(L)), where L is the length of the bit string that you're storing. That's a huge improvement.

[calcyman]

This is just to say that there is another way to get a constant-time read with a 1D tape of still-lifes: use two stacks instead of a tape (with the top of the stack nearest to the computer) and design spaceship salvos which push/pull the tape of still-lifes. Probably the cheapest technology to use here is Cordership salvos, and where the tape consists of still-lifes positioned at multiples of 8fd. If you want to avoid leaking Corderships off to infinity, then you'll need some kind of absorber at the end of the tape, which is also pushed/pulled.

[nalA]

Better support for subroutines would be one of the big advantages of a 2D program memory. Each subroutine could easily be stored in its own row in a rectangular memory block. Reading a different subroutine would be just a quick adjustment, bumping one of the two read heads forward or back a few rows, and resetting the other read head to zero.

Yes, that's similar to what I was thinking:

However I can indeed reformat the still-life tape into a 2D form, like 4 bytes in a row; it could help, but not much.

However, when a subroutine is too long, extra "line breaks" might be needed for performance issues, while the problem of where to add those line breaks is left to the programmers. It's somewhat not elegant. What I was thinking yesterday was setting a maximum line width, however that maximum is hard to choose. Anyway, as this could be easily (well, compared to others) implemented with APGsembly, I'm taking it as a last option.

Or each subroutine could be stored in its own NxN area, instead. For example, we could build a mechanism that quickly adjusts the X and Y read heads to point to a given block, then reads out all of the bits in that block and produces a glider stream to be processed elsewhere.

That sounds interesting. I wonder how to read from a 2D area continuously.

You definitely start seeing the same old problem with longer wait times for retrieving faraway subroutines, but honestly HashLife is really good at speeding up the boring parts so that designs like that would still be runnable in Golly.

Indeed. The clock period might need to be big, but it's not really a problem with HashLife. I will try to build a 1D tape version first.

[dvgrn]

Or each subroutine could be stored in its own NxN area, instead. For example, we could build a mechanism that quickly adjusts the X and Y read heads to point to a given block, then reads out all of the bits in that block and produces a glider stream to be processed elsewhere.

That sounds interesting. I wonder how to read from a 2D area continuously.

First you'd pick a block size that worked for whatever you want to store -- a good-sized subroutine, maybe 4K bits? So the blocks would be 64x64.

The bit reading could be done with a "reset to start of block" mechanism after each of the 64 scans of one row. Or, with only a slightly more complicated mechanism, you could store and retrieve data in each block boustrophedonically -- read up one row, bump up one column, read down the next row, and repeat that 32 tiimes. Mechanisms could easily be designed that would copy the contents of one block to another block with that back-and-forth method.

I suppose reading each block in a spiral out from the center, or in toward the center, would take a mechanism of about the same level of complexity.

There would be a slight Doppler effect with either the boustrophedonic or spiral methods -- the output would be _fairly_ regular, but some sequences of bits would arrive at the processor slightly closer together than other sequences. If it's necessary for the bit-read results to arrive somewhere with precise timing, that can be arranged by adding in an appropriately timed universal regulator.