factorio-turing-complete

We reduce from 2-Register Minsky Machines. These are a special kind of register machines (or counter machines). These machines are well-studied, very simple and are often modelled in formal proof systems if one wanted to make the proof mechanized and formal. Example: Model in Isabelle HOL, 2MM Model in Rocq's Library of Undecidability.

The idea is: We have a program and a PC (just like in RiscV), as well as two registers (unbounded) A and B. We have two/three possible instructions:

• Increment (and jump to a PC)
• Decrement (and jump to a PC), if the register is already zero, do not decrement and jump to another instruction
• Halt the program

You might see how Decrement is special: Is works like a jump if zero instruction and with a bit of thought, you might be able to implementa loop with it. It turns out that we can in fact compute everything Turing Machines or assembly or any of our other computation models can compute with these instructions alone. In the simplest model, the "and jump to a PC" part (except for the Decrement alternative) is just the next PC but I want to keep the model a bit more general because I can.

How do we model this in Factorio?

We have the combinator values we can use for the registers:

• 🄰: Our first register
• 🄱: Our second register
• 🄿: The PC (represents which instruction to execute)
• We use a few other values for intermediate computations (🄼,🄽,🄾)

The general idea is: Build a combinator block that outputs nothing if the PC is not correct. Otherwise, transform the register depending on the instruction (e.g. set the new PC) and output the other values as it. So, we create a modular block for each of the three instructions above.

The check can be performed by a decider combinator on 🄿: We use 🄼 to indicate that the current block should be executed. We could in the next combinators of the block reuse 🄿=?0 but I wanted to avoid redundancy.

At the end of the block, we will output the new values guarded by our condition: You can see: We will use the $\color{red}\text{red}$ channel for the control signal and $\color{green}\text{green}$ for the (new) register values.

Increment A/B

We want to add $1$ to the corresponding register value (let's say 🄰 for this example). We could use an arithmetic combinator. But I find it easier to use the fact that Factorio sums up connected signals. So I transmit the values of 🄰 and 🄱 and add a constant combinator with the new PC value in 🄿 as well as $1$ in 🄰.

1: the constant combinator to add to 🄰 2: the pass-through decider combinator that keeps only the values of 🄰 and 🄱 (and discards 🄿 to be overwritten with the new PC) 3: is the PC selector from above and 4: is the guard that only lets the new register values through if the instruction is at the correct PC

Decrement and Jump

The decrement is a bit trickier. Let's use 🄱 for this example. We have two cases: If 🄱 is zero, (tested by a decider combinator (1)), we set a signal 🄽, copy 🄰 and 🄱 and set the else PC to 🄿 (2). We test the condition 🄽 in the guard (3). If 🄱 is not zero (tested in (4)), we set 🄾, copy 🄰 and 🄱, and set the then PC to 🄿 (5). Additionally, we output $-1$ in 🄱 with the constant combinator (5) to decrement 🄱. Finally, we also test the condition 🄾 in a second guard (6).

Example program

0 INC(A,1)
1 INC(A,2)
2 DEC(B,4,3)
3 INC(B,4)
4 INC(B,5)
5 DEC(B,6,7)
6 INC(A,7)
7 HALT

We encode the program accordingly as The instructions are stored in 1-8 respectively. Instruction $8$ sets 🄿 to -1. In (9), I test if 🄿 is -1 and if so, copy over the register values. This is a normal combinator trap that keep the values at the end of the program for the user to look at. In (10), all values are just copied over if 🅁 is not set. If it is set, nothing is copied, resetting the whole state to all zeros.

You can test it out here. The result should be

P=0,A=0,B=0
P=1,A=1,B=0
P=2,A=2,B=0
P=4,A=2,B=0
P=5,A=2,B=1
P=7,A=2,B=0

Extensions

One could be fancy and create a parametrized blueprint like this that takes the PC values as arguments.

One could also write a program to automatically generate a blueprint for a program. After all, Factorio blueprints are just zlib compressed base64 encoded json strings:

def parse_blueprint(encoded_str):
  encoded_str = encoded_str[1:]
  compressed_data = base64.b64decode(encoded_str)
  inflated_data = zlib.decompress(compressed_data)
  return json.loads(inflated_data.decode('utf-8'))

Finally, one could create a unified module for an instruction that would decide, depending on a constant combinator value, which instruction it is.

Side Note: A 1-register machine with some more clever instructions also work -- the proof is quite easy.

Second part of my comment

Without combinators, there is no way. We always can only affect a limited area be it with inserters, trains, ... And each of our storage is finite. We have only a finite amount of space we can influence and even with chests, we can not do much. In theoretical computer science, there is the (not too hard) result that with finite space, you can only perform finite actions before you loop or exit (as the state has to repeat).

To have turning completeness without our unbound combinator values, we need more advanced methods as for instance

• https://mods.factorio.com/mod/recursive-blueprints
• or even https://mods.factorio.com/mod/deep-storage-unit (together with infinite ore-patches)

offer.