Forum

> > CS2D > Maps/Editor > Proving the Turing Completeness of CS2D Maps
Forums overviewCS2D overview Maps/Editor overviewLog in to reply

English Proving the Turing Completeness of CS2D Maps

10 replies
To the start Previous 1 Next To the start

old Proving the Turing Completeness of CS2D Maps

Qb
User Off Offline

Quote
In the following post I go through proving Turing completeness in CS2D's maps without using lua.
What is Turing Completeness? >
Why did I do it? >

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:
IMG:https://i.imgur.com/03RrlVE.png

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.

IMG:https://i.imgur.com/bQpTmh6.gif

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.
Images of the Map in the Editor >


You can download the map here: file cs2d Rule 110 in CS2D

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.
The Script and its Results >


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

old Re: Proving the Turing Completeness of CS2D Maps

_Yank
User Off Offline

Quote
Cool, we're emulating a primitive computer inside CS2D!
I'll look into it, nice gem. Any idea on what could be done or achieved with this, apart from the fun while doing and learning it (not the turing completeness, rule 110) ?
edited 2×, last 12.08.17 01:50:28 am

old Re: Proving the Turing Completeness of CS2D Maps

Qb
User Off Offline

Quote
In theory it could be used to implement any definable algorithm (given an infinitely large map + the right starting cell configuration). But it is by no means practical to do so using rule 110. It's far to large and convoluted to be of practical use. Also there's map lua scripts which can also perform any algorithm so it's even less useful. It's just for fun anyways, so .. whatever!
edited 1×, last 12.08.17 04:24:32 pm

old Re: Proving the Turing Completeness of CS2D Maps

DC
Admin Off Offline

Quote
Crazy stuff. Glad to see that CS2D didn't explode entirely in this experiment and also glad to hear that CS2D was a motivator for you regarding that computer science and programming stuff

old Re: Proving the Turing Completeness of CS2D Maps

Loooser
User Off Offline

Quote
Very cool. The cs2d if-trigger was a great extension it gives mappers the opportunity to create behaviors that already feel like a script. I think the cs2d map editor is very well made and gives us a lot of flexibility. It's just a matter of arranging the entities to fit them all on the map

old Re: Proving the Turing Completeness of CS2D Maps

Qb
User Off Offline

Quote
Glad you folks seem to like it. I'm currently working on a bigger machine on a CS2D Map. I've been playing around with counter machines recently.

IMG:https://u.biyori.moe/XV8ewQEr.gif
IMG:https://i.imgur.com/7BAcdA2.png
IMG:https://i.imgur.com/mrtDhWr.png

This is an 8-bit binary counter with an incrementation(left) and a decrementation function(right). It has been hooked up to a clock in this GIF.
To the start Previous 1 Next To the start
Log in to reply Maps/Editor overviewCS2D overviewForums overview