User:Larix/MPL/6

Excursus: signalless logic

Machinery in Dwarf Fortress is commonly controlled by levers or pressure plates, constructions which send signals. Dwarven computers commonly use signal input and signal processing to produce an output, which also commonly consist of signals or directly signal-controlled events like raising and retracting spikes or opening/closing doors to the magmaduct.

When playing around with minecart logic, i wondered whether there might be other options, though: after all, a wooden cart smacking into an aluminium cart results in much less outgoing speed than a copper cart propelling the aluminium cart. In addition, the "pushing" cart will not stop in the place formerly occupied by the pushed cart, but rather in the adjacent tile - and it will not stop if it encounters no cart to push. Based on those ideas, i experimented with a logic paradigm using nothing but minecart collisions as decisive interactions, needing no signals to work at all.

I've only produced some very basic proofs of concept to show that such logic has the potential to be used in computation. Building any machines emulating classic logic gates and computer components would probably be a fool's errand, the basic interactions simply don't fit those paradigms and quickly result in phantasmagoric monstrosities in construction.

Basic operations

I'm only going to show collisions between one moving and one standing minecart. Those are easy enough to understand and work with.

.

■

═

═

═

■

═

b

e

f

o

r

e

.

═

═

═

■

═

■

a

f

t

e

r

.

The green cart comes from the left, pushes the yellow cart and stops while the yellow cart moves on. This is in fact the basic outcome of a minecart collision. We can run a series of minecarts over this track and eventually, the stationary cart will occupy the start of the track. Effectively, we could count down like this, but nothing of interest would happen if we reached zero.

Having just another new stationary cart is rarely of interest, but we can change the architecture so that an incoming cart encountering a stationary cart in its way will not stop in the adjacent square - because that square itself forces the minecart to move. This means letting the arriving cart move over an upward ramp or making it jump over a hole. If it encounters and pushes a stationary cart, it will stop in its current square and either fall down to a lower z-level or roll down the ramp.

So we get those two basic functions:

.

O

O

║

║

■

║

■

║

▼

║

▼

║

d

e

l

e

t

e

s

p

a

w

n

A cart moves in from the south, across the ramp. If the place directly outside the ramp is occupied, the incoming cart stops and rolls down the ramp. If the place is empty, the incoming cart climbs up the ramp and rolls over the tile to the north. In the "delete" example, the incoming cart will be reflected and keeps moving if the place is occupied. If the place is free, it bumps into the limiting wall and stops moving. If this "gate" is empty, it "deletes" the moving cart - and becomes occupied.

In the "spawn" example, the incoming cart will also stop and roll down the ramp if the tile above the ramp is occupied, but the cart which stood there will move off the square and leave to the north. If the place is empty, the incoming cart itself will pass to the north. This "gate", if occupied, "spawns" an additional moving cart, while becoming empty.

Of course, variations on these concepts are possible: a spawn gate can be combined with a length of track with a standing cart originally placed several tiles away from the ramp. When a series of carts is sent over the ramp, there'll always be an output cart, but the location of the standing cart will keep moving closer to the ramp. Effectively, such a track will "count down" until at zero it spawns a cart rolling off the ramp. Multiple carts can await a collision, and the collision may reconfigure the queue following Newton's cradle principles.

Pathing and regulation

Those two basic operations by themselves offer very little. It takes proper combination and direction to make them do something interesting.

In spawn gates, a moving cart leaving the gate will always be generated. You might wish to replace the stationary cart after the spawned cart has done its thing. This can be done by a simple loop coming in from a different direction:

.

║

║

O

■

═

═

╗

O

║

═

═

╗

▼

║

║

║

▼

║

║

║

╚

═

B

.

B

.

╚

═

B

.

B

.

║

║

s

t

a

t

e

r

e

s

t

o

r

a

t

i

o

n

A spawned cart goes through the Black Box (B.B.) to attend to other business, then goes over the track loop and bumps into the western wall, taking up the occupancy slot. If the gate was empty, the incoming cart will pass right through, no black box process is performed and the gate remains empty. As another option, a delete gate can be put in the way of a moving cart, which gets emptied by a perpendicular spawn gate built over the same core grid. The next time a cart checks the delete gate, it stops and doesn't move on.

Carts can be placed back into gate slots not only by ordinary loops but also by lifting the cart to the level above and dropping it through a hole in the floor. This allows to approach a single tile from all four possible directions, opening some avenues for complexer circuits.

Application

The core machine logic devices are heinously complicated to build from these basic components. It can be done, but it's deeply impractical:

.

o

n

e

b

O

║

╔

═

▼

▼

╝

╗

║

▼

║

║

▼

║

║

╚

═

═

═

╬

═

z

e

r

o

a

╚

║

O

║

▼

║

▼

║

╚

═

═

═

╝

║

b

a

s

i

c

b

i

f

u

r

c

a

t

i

o

n

There's only one target cart in the system, which resides either at a or b. The circuit only checks whether the spawn gate at a is occupied and returns a "one" if yes, a "zero" if no. No matter whether this is the case, there'll always be a cart leaving from a to the north. If it's the target cart, it will find an empty slot at b and stops there. The spawned input-collector cart will now go around the outer loop. pushes the target cart back into position a and leaves towards the "one" direction. If a was empty, the input-collector will pass it, goes to the north, checks the delete gate at b and finds it occupied by the target cart and leaves in the "zero" direction. Funnily enough, almost the same circuit with opposite "reset" pathing will always toggle the state of the circuit (and still has two separate outputs), offering an extremely high-speed low-tech incrementer.

I also built a read-/writable binary "memory cell" based on this principle. It uses the same basic bifurcation, using the "state restoration" paradigm from above to restore the memory state after reading, and weight-/speed-based differentiation to "write" (i.e. toggle or leave unaltered). "Storage" and "reader" cart should be the same weight (they'll also switch role on each read event), while the "writing" cart must be significantly lighter to keep toggles and "empty writes" (i.e. memory was already in the desired state) apart. It works flawlessly, but is of course impressively large, complicated and slow. Three minecarts out of five, wouldn't build a megabyte memory out of these.

Technically, i think it should be possible to build most classic logic gates simply by combining several of these identity testers with proper paths; apart from XOR and XNOR, each individual logic gate should take four spawn and two delete gates. No competition for any discipline of signal-based logic.

I managed to build a NAND/OR gate from these components, but it's not pretty. Fun to look at, but ridiculously large - it takes four spawn and three delete gates to operate.

Since weight differences can greatly alter the resultant speed after collisions, it's possible to modify the spawn gate so that it alone suffices for an identity check/bifurcation:

z

e

r

o

o

n

e

║

║

a

║

║

▼

║

▼

║

╚

═

═

╝

║

i

n

w

e

i

g

h

t

-

r

e

g

u

l

a

t

e

d

b

i

f

u

r

c

a

t

i

o

n

A lightweight cart is sent into the gate from the south, checking whether location a is occupied or not. The crucial point is that a very heavy cart is used to occupy the slot. I used a wooden cart as input and a wooden cart full of water, on top of a medium-friction track stop, as "marker". The input cart could never give enough of a push to move the marker off the check location. This gate will thus only ever output the input cart itself, on either of the two output branches, depending on whether or not a is occupied. Carts can be filled with or emptied of water without needing signals or power, as long as you have an infinite water source available.

Where this type of logic looks attractive, though, is in applications where counting and sequential operations take place. As mentioned, toggling and thus counting by increment should be comparatively quite fast. A count-down track can be used to regulate conditional loops, replacement loops can be used in binary incrementers.

Computing by speed

A much more fiddly application is to use carts of varying weights and speeds in collisions and using the outgoing speed as basis for computation. Carts of different speeds can path differently - the best-known example are probably derailing carts: past 50 000 speed, carts will only follow a corner if there's a wall or path-blocking building behind it, otherwise, they pass in a straight line. If different output speeds can be generated in a collision and both speeds above and below the derail threshold are possible, a simple not-backed track corner can already separate speedy from slower carts. In addition, placing braking architecture like track stops and ramps can help separate different-speed derailing carts and perpendicular downward ramps can separate below-derail carts. Offering different paths for the different speeds allows performing different operations depending on the "input" - consisting of the momentum of the incoming and the weight of the pushed cart.

I used this principle first and it shows most promise for more conventional applications like memory and logic gates. Getting three distinct results out of a single collision was already quite doable; four was harder, but still possible. I managed to build a full adder on this principle, the addition itself really being a single minecart collision which was then separated into the four possible results just by track and constructions.

Outlook

Signalless logic is as yet more a funny concept than a really useful computing paradigm. I find it interesting to know that some "proper" computing procedures like binary addition, bit shift operations and program loops can be built and controlled without using a single mechanism, which flies in the face of classical dwarfputing, which measures its dwarfiness by number of mechanisms installed.

As mentioned above, the independence from signal and building timeouts suggests there might be some potential to integrate signalless processing into conventional computers, performing sequential operations at high speed without switch lag and handing over the results to signal processing again.