It is probably not much of a surprise that CS2D maps are Turing complete this becomes even more obvious when you realize that Turing completeness doesn't need a high degree of complexity. This becomes very apparent when looking at other simple Turing complete systems such as Brainfuck, Lambda Calulus and FRACTRAN (see also: Greenspun's tenth rule).
I prove the Turing completeness by implementing a simulation of another Turing complete system. There is are multiple well known systems that are Turing complete such as Lambda Calculus, Counter Machines or John Conway's Game of Life but I go for a simpler one. Rule 110 is a simple one-dimensional elementary cellular automaton that is (computationally) universal.
Simply put, it is a straight line of cells next to one another. Each cell can have 2 states "0" or "1" which can also be interpreted as "off" and "on". Each generation certain rules are applied to each cell determine their next state. The rules take the cells current state as well as the states of the left and right neighbors into account. The following rules are applied:
Or in other words: If a cell and both of its neighbors are 1 the cell becomes 0. If a cell and it's right neighbor are 0 it stays 0. In all other cases the cell becomes/stays 1.
So how do we implement this using the map editor? It's fairly easy. To represent the current state of a cell we use Dynamic Walls. If they are visible that means the state is 1. We use another Dynamic Wall as a temporary storage for advancing a generation.
Using chained If-Triggers we can determine the next state of the cell by checking if either of these applies:
The entity at position of the dynamic wall representing the current state of the cell to the left is visible AND(using chained if) the entity at position of the dynamic wall representing the current state of the cell in question is visible AND the entity at position of the dynamic wall representing the current state of the cell to the right is visible
The entity at position of the dynamic wall representing the current state of the cell in question is not visible AND the entity at position of the dynamic wall representing the current state of the cell to the right is not visible
If so we trigger the Dynamic Wall serving as the next generation buffer for the cell in question. By having this Dynamic Wall visible(1) by default we turn it off(0).
Next we reset the "current state" to only contain "0"s. We can do that because we already have the next generation buffered. We do that by using If-Triggers that only trigger the "current state" wall if it's visible.
Then we proceed by writing the "next generation" walls to the "current generation" walls. This can be done by triggering the "current generation" walls only if the corresponding "next generation" walls are visible(1). Since the "current generation" is completely off(0) this will result in turning the corresponding walls on(1).
After that we reset the "next generation" buffer to be all "1"s by only triggering the walls if they are not visible(0).
One generation was now successfully advanced. Rinse and repeat.
An idealized version of CS2D that would support infinitely large maps, entity names, trigger names and amounts of entities would be Turing complete. But such a limited implementation is as close as we can get. In reality there is no Turing complete machine because such a machine would need to have infinite memory which is physically impossible.
The image above shows a working implementation that works the way I just described it, the "IN"-tiles representing the current generation and the "OUT"-tiles representing the next generation buffer. The "RS"-tiles are the If-Triggers for resetting the "current generation" walls(top row) and the "next generation" walls(bottom row). The "PUSH"-tiles are the If-Triggers that write the next generation buffer to the current generation. The arrow tiles(see below) are the chained If-Triggers that determine the next generation. The direction of the arrows shows which neighbor they are checking, the dot meaning they check their corresponding "current generation" wall's state.
You can download the map here: Rule 110 in CS2D (5)
I also made a lua script that automatically outputs the complete current generation to the console if "LUA:SCAN" is triggered. The clock advancing the generation automatically does just that.
I hope you like what I did and maybe even learned a thing or two. Have a nice day!
Necro
edited 2×, last 12.08.17 12:18:59 pm