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.

Exploiting jumping carts, a "toggle" gate is also possible:

.

O

O

╔

═

■

═

▼

▼

═

╝

+

+

║

■

t

o

g

g

l

e

.

The operating cart arrives from south, with a speed of 35000+. Since the tile immediately south of the pit is ordinary floor, the cart will not enter the pit but jumps instead. If the SE corner next to the wall is occupied, the operating cart pushes the occupant off around the corner, falls into the pit and accelerates west. If the corner is unoccupied, the operating cart keeps flying until it is stopped by the wall, allowing it to settle onto the corner tile without rolling off. The occupation status of this gate changes to the opposite everytime it is tested. Notably, it produces no output when changing from empty to occupied, but a double output when changing from occupied to empty.

Of course, variations on these concepts are possible: one and the same location can be accessed from multiple sides, under different doctrines - e.g. a delete gate that can be emptied by carts approaching from another direction, operating as a spawn gate for them. 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, 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.

Signalless circuits can count inputs sent via minecart push, and they can count such signals at speeds much higher than the ~100 steps dictated by pressure plate recovery. The fastest i managed to create is a ternary counter that can handle input periods all the way down to 27 game steps. It sends a "carry" whenever the circuit itself "overflows", on every third input:

z

+

0

z

-

1

.

.

╔

╗

.

.

╔

╝

#

#

#

.

.

▼

#

║

#

.

.

▼

#

║

#

.

╔

╣

#

#

#

#

.

║

▼

╔

═

═

╗

.

╩

#

#

#

#

#

#

║

▼

▼

╩

▼

▼

╝

#

╦

═

#

╔

═

#

.

╚

╝

#

║

#

#

#

#

#

#

#

The double-ramp pit with return loop to the north, when supplied with one minecart, provides regular pushes to the cart just south of it, with a period of exactly 27 steps. After each push, the oscillating cart accelerates down the ramp going north, reaching a speed of ~ 39.000. It climbs the ramp to the north in a single step thanks to the checkpoint effect, returns through the loop and enters the pit again from the north, accelerating towards the south now. In the end, it delivers a push to a cart standing on the level floor (NSW track) just south of the oscillator pit, with a speed just under 50.000.

The track loop directly south of the oscillator contains two minecarts, one on the tile directly on the oscillator exit, the other in one of three possible positions somewhere on the track loop, depending on the current count. The cart that gets pushed by the oscillator rolls onto the WNE ramp. Since that ramp is connected to wall (N and E) and has exactly one floor connection (W), it accelerates to the west. The southward speed remains unchanged and carries the cart off the ramp and onto the adjacent SEW ramp after three steps, before the westward speed carries it off west. On the SEW ramp, walls are to the S and W, and floor to the east, so acceleration goes to the east now. Thanks to the checkpoint effect, the cart climbs up the ramp to the south in a single step if the southern tile just outside the pit is unobstructed. The cart then properly takes the SW corner, turning around to the west. It pushes the other cart present in the loop and comes to rest on the adjacent square. The second cart finishes the course and comes to rest on the tile south of the oscillator in time to take the next push.

If the secondary counting cart stands on the "exit" tile of the pit, the arriving cart pushes it without leaving the pit. It will then accelerate to the east, passes across the adjacent EW track ramp in a single step (due to checkpoint effect) again and pushes the cart in the next counting circuit, before it accelerates to the west, climbs the SEW ramp in one step and leaves the pit to the west, coming to rest against the wall there. The circuit has passed on a signal and can accept new input, sending the next "carry" once three more inputs have been received.

This circuit is tailored to the behaviours of colliding carts: the minecart engine keeps track of "sub-coordinates" of a cart on its current tile, and the durations of acceleration and effects of diagonal movement depend very much on these, not directly visible, exact locations. Furthermore, collisions - both with other minecarts and with walls - stop a cart at the very border of its tile in the direction where collision took place. The carts on the oscillator output are practically scraping on the wall, thus the odd WNE ramp: a certain amount of west shift is necessary to enable proper operation.

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.