Sticks and Stones
Sticks and Stones is an attempt at a simple physical, analog computational system that has a chance of implementing a Minsky machine using objects you might find on a beach. Designed very quickly in a flash of inspiration, so it likely falls short of that goal, and should be considered a work in progress.
Memory system
Three stones on a 2D plane (e.g. a beach). One Amethyst, one Beryl, one Chalcedony. Initially they start adjacent to each other so that every stone has exactly one point touching each other stone. Amethyst is placed north, Beryl is east of Chalcedony.
A C B
Syntax
Sticks of any length, made from three types of tree: Ash, Birch, and Cedar. Sticks are laid end to end, at any angle, from a starting point. Every stick represents a vector, with a direction, magnitude, and clear start and end points.
The sticks are used to translate the corresponding stones by the represented vector.
- Ash moves Amethyst
- Birch moves Beryl
- Cedar moves Chalcedony
Control flow
Branch if touching : ├
This is based on the nested conditional looping construct found in bf [] although the entry condition is inverted to allow the main branch to be entered from the initial state.
Branches of sticks, represented by sticks branching off from the middle of a stick in the current branch, ├, are entered into if any of the stones are touching. At the end of a branch, execution returns to the start and the branch is repeated if again any of the stones are touching, otherwise the parent stick is executed and the parent branch continued.
A stick with a branch from it is only executed after the branch from it is complete, or immediately if the branch is never entered.
Branch to closest : Y
If multiple sticks start at the endpoint of the prior stick, Y, find the mid-point of the triangle formed by the stones. The stick of the wood representing the stone closest to the mid-point is taken. If there are multiple sticks of the same chosen wood, one is chosen non-deterministically.
It is likely that sticks will cross and overlap. This is acceptable, and sticks can be laid over the top of each other. Care should be taken that these overlays cannot be confused with branches from lower levels.
Loops are possible when sticks are joined end to end in a circuit. Flowing back against the stick vector direction is prohibited by default, but it may be useful to enable this so stone movements can be inverted?
Architecture of a Sticks and Stones based system
The stones and sticks are intended to be placed on separate parts of a sufficiently large beach, or at least should not interfere with each other (Harvard architecture). The basic Sticks and Stones processor is concerned solely with moving the stones based on the layout of sticks. Other functions should be handled by additional units.
Interpretation and output is the domain of the:
Lithomancer
A Lithomancer may only read the stones, and cannot influence their position in any way. Additionally, the Lithomancer can neither read nor modify the sticks.
A particular Lithomancer has a set of rules that maps triggers to output. After each processor cycle, if the Lithomancer observed a trigger, it adds the interpreted tokens to the output stream.
Triggers can be specified on distances between the stones, absolute positions of the stones, angles between the stones and/or origin, by exact values or thresholds (=><). Triggers can be combined linearly.
Output values are fixed strings, or numbers / integers / characters determined by linear combinations of the same parameters available to triggers.
Other potential roles
Lithourge; title for an input-device or unit than can move the stones independently of the sticks. Currently hypothetical. Sounds like hubris and should be avoided.
Rhabdourge; role-title for one-who-can-move-the-sticks. Some kind of stick meta-programmer? Potentially quite powerful when combined with Lithomancy.
Computational class
The design intent was to make this simple model Turing complete by providing three length 'registers', A-B, B-C, C-A, two of which could be fully independent. It seems likely that the branch-if-adjacent mechanism spoils this by losing the value of one register when the stones are brought together, which is why 'branch-to-closest' was added. Neither has been properly tested yet. I was hoping there was a way to use relative angles around one stone to store and retrieve information, but have not yet figured out how to take advantage of this. The branch mechanisms may need to be tweaked to make the model more flexible. I do not want to add more stones. I thought about adding a z-dimension, but would rather not. I have not decided what the behaviour of colliding stones is and whether one stone could push another, or overlap. Deciding either way may add some power. The intent is for this to be a fully realisable physical model, with real sticks and stones, so that should drive any further developments.
I feel that there is something missing from, or blocked by, the current spec preventing Turing completeness. Figuring it out a minimal change from the current spec to enable this is an open challenge for this work-in-progress.
Examples
Some form of notation is needed to describe the stick layouts.
Provisional notation Sticks are x,y pairs separated by the stick type a,b,c representing the vector endpoint.
├ ┤ branches split off from the midpoint of the previous stick.
Fork branches can be represented like numbered labels Y1 and join to corresponding Y1: on separate lines.
Colours for graphing
- Ash - Amethyst: (Magenta/Blue)
#CC00FF - Birch - Beryl: (Cyan/Green)
#00FFCC - Cedar - Chalcedony: (Yellow/Red)
#FFCC00
Truth-machine
Here is a truth-machine layout as an image and in provisional vector notation.
{1b0 | 0b0} 3c0 2a48.01 1c0 ├ 0a1 2c2 0c-2 -2c0 ┤ 3c0 0c-0.1 -3.1c0
For input 1, start with a birch stick of length one (marked |), for input 0, remove it (marked O). Output is to be interpreted using the Lithomancy: !BC:c_AB -- read the distance between Amethyst and Beryl when Chalcedony touches Beryl. The long slightly angled ash stick creates a separation of ASCII code 48 = 0 between Amethyst and Beryl.
Hello, World!
Playing with the output hack and notation, here is the classic Hello, World! using 38 sticks and 3 stones:
-1c a72 1c 3c a29 -1c -3c a7 1c c-2 2c2 1c a3 -1c 8c8 a-67 -8c-8 -3c a-12 1c 3c a55 -1c -3c a24 1c 3c a3 -1c -3c a-6 1c 3c a-8 -1c -3c a-67 1c
Output:
Hello, World! Final state: A: (0.0, 34.117999999999995) B: (0.5, 0) C: (-0.5, 0.0)
External resources
- Very minimal partial interpreter for the vector notation in python3. Has character output but no control flow.