The Turing Train (aka fully functional Turing machine using trains)

Hares · Post by **Hares** » Wed Dec 25, 2024 1:40 am

Well, I did it.
Behold, The Mighty, The Turing Train!

The Turing Train

So, the rules for The Turing Train are as follows:

A tape is represented by an arbitrary large straight railway track with no rail signals or any other control units besides the train stops which are always enabled.
A cell on that tape is represented by a chest that can hold a single item from the alphabet (or hold no item).
A moving head is represented by a double-headed train that can move in either direction towards any neighboring train stop, as well as do no move.
A state register is represented by a contents of the train cargo. Any positive number represents state ID, while zero items represents finished state.
A finite table of instructions is a grid of constant combinators, three for each state -- one for choice of what to write; one for choice of the next state, and one for choice of the next movement.

The Journey

I got hit by that idea a few days ago while discussing combinators (ref: 124776: Combinator cookbook 2.0) and train not wanting to leave their own train stop (ref: 118475: [2.0.12] Train does not move between stops with same name (MR)), so that got me thinking if I can combine both of these knowledges together.

The idea of almost or completely circuitless TM (ref: https://youtu.be/b1PlPG2vUjY) was rejected almost instantly as there would be little to no control on the train cargo (program was supposed to be written in the list of interrupts, and the states was represented by different parallel tracks for the train).

The next idea was to make a completely stateless set of combinators for that Turing machine with the single head processor (non-moving, sadly), but after making proof of concept and failing time after time I decided that my TTT can have them as long as they do not carry states between the train stops:

One on each train stop, counting time since train arrival to prevent the write operation before the combinators finish their calculations
One on the head processor, for storing the train state on the moment of its arrival to guarantee only one change per step

There's also a shared wiring between all train stop cells and the processor:

Copper wire used to carry electricity from the infinite source on the processor to the train stops
Red wire carries signal from the head to the processor
Green wire carries signal from the processor back to the head

The Processor

The processor itself is relatively simple:

: Head processor overview; 12-25-2024, 03-43-11.png (1.31 MiB) Viewed 130 times

At first, it reads if the train arrived to the train stop, and if it is, remembers the current state (S for state and symbol from the alphabet for the cell value) until train leaves that train stop. All signals are logical. Then, it uses a simplest grid mapping for the state: after a set of three combinators representing instructions of the current state is chosen (states instructions can be extended almost infinitely to the right), these are mapped from the current cell value to a new one. Empty cells are represented by a special non-item guard signal of red cross (

). For all of these, a key in the map is current value as signal ID, and value of that signal is as follows:

For the write value mapping, value of the signal in the mapping is symbol ID in the alphabet, or -1 for value erasing. For example, in my alphabet (blueprint parameters 0 to 9 -- thanks Wube these are items!) numbers 1-9 have ID of 1-9, and number 0 has ID of 10. (Factorio doesn't like zero-value signals) The result is decoded to be signal type and not symbol ID.
For the change state mapping, value of the signal in the mapping is target state, or negative value for the program termination. Technically, program will be also finished on zero-value target state, but I tried to avoid any zero-value signals. The result is encoded as S.
For the target direction mapping, the possible values are +1 for moving right, -1 for moving left, or 0 (this time it was perfectly fine, BTW). The result is encoded as signal D.

: Example: Mappings of old cell values for the new ones in state Q2; 12-25-2024, 03-53-48.png (688.54 KiB) Viewed 130 times

The Moving Train

The moving train is also very simple.
It's has empty schedule and its list of interrupts includes:

: Train schedule overview; 12-25-2024, 04-04-24.png (100.8 KiB) Viewed 130 times

Start. Does nothing, just asks train to enter automatic mode and attach to the train stop it's currently parked in.
Move Right. Asks train to move right and then park.
Move Left. Asks train to move left and then park. Are you surprised?
Wait. Train remains parked on the current train stop while also re-attaching to it (re-triggering enter event).

Why are there extra train stops? Because in 2.0, trains don't like to move to a different train stop when they are parked on the train stop with target name, even if it becomes disabled. However, even though I dislike that behaviour most of the time, here it was kinda savor by letting me implement "Wait" interrupt without actually moving the train. Thus, a cell always have 4 train stops. Which leads to us to the...

BTW, I made this with the raiguard's beautiful Editor Extensions mod, as well as couple of others QoL, but removed them before publishing the map.

The Tape Cell

: Tape cell overview; 12-25-2024, 04-19-02.png (724.89 KiB) Viewed 130 times

The tape cell is the most-complicated entity here. Even though it has only few combinators, it was a pure wiring hell. Firstly, I needed to make sure train will never reach its own cell by moving the opposite direction, so the entire cell is slightly shorter such that "backside" locomotive cannot already touches the opposite direction train stop. Then, I needed to ensure that the cell propagates its value to the head processor only when its occupied by the train, but regardless of direction that train came in -- so, both train stops are joined by a single wiring and have exactly the same settings besides name & color.

Then, there's two sets of inserters interacting with the infinity chests. One set is dedicated to writing the current cell value and it utilizes the set filter (whitelist/blacklist) modes from the circuit network and the fact the erase item signal is non-item. The other interacts with the train directly and moves/removes "Science Pack" dummies (thanks Wube these are real item with the stack size of 1!) to/from the wagon until their number matches the state.

Initially, I wanted carry alphabet characters on the infinite wagon of train instead of storing them in chest, but, unfortunately, it ruined "Inactivity" wait condition. Of course, I could make "Time passed" condition or "Circuit network" condition, but the first can ruin big state shift (i.e., if I move from the state 1 to the state 40 it's 39 inserter swings), and the second required additional logic & wiring which I tried to avoid.

The Result

The result is fascinating. It took me only about 8 hours set up from zero to hero, and it works almost flawlessly.
The only problems I noticed are:

You cannot provide no signals in the states table for the purpose of "the same" result, you must "rewrite" current value
If the train reenters the same train stop, even though it's result is as expected, the process includes changing items from the wrong state and only after that inserting the correct item as the train appears on the train stop so fast the combinators does not reset
The "Program ended" diode is not working; the "Program ended" beep sounds upon reaching the last instruction and not resolving it.

The attached savefile implements classical numbers incrementor (adds one to the input number), as well as the turing machine program I used as a reference (which I stole from one educational site's with the Turing Machine emulator). If you want to experience it yourself, download the savefile (no Space Age nor mods are needed), enter any number by putting blueprint parameters (have I thanked Wube for these being items with the stack size of one already?) to the boxes (and extending the train track if needed), and then pressing Start on the train. If you want to restart (i.e., for another number increment), you need to return the train to its initial state by putting exactly one science pack item to the cargo wagon.

Technically, it is possible to write a converter from that program to a Factorio-compatible blueprint (I did the similar as recently as today for writing text with the constant combinators), but I'm too lazy to do so.