Critter World is Turing Complete - A Not-So-Rigorous Proof
Critter World is Cornell's CS 2112's Final Project. It is a simulated hexagon world where critters, controled by programs, can move, eat, mate, bud, attack, etc. The programming language is very primitive and not Turing complete, but it's still useful and expressive enough to cleverly control one step of a critter move. You can see the spec publicly here.
Although the critter language is not Turing complete, a running critter world simulation, under some circumstances, can be used to simulate a Turing machine, thus making it Turing complete.
#
Assumptions and ModificationsFor the convenience of proof, we will make some assumptions:
- Critters have infinite amount of energy.
- Some tasks can be done immediately. e.g. two consecutive turn around, turn back, etc.
- Critters are allowed to perform multiple actions at once.
Note that these assumptions are not really needed. If these assumptions are not true, we can simply use some of critter's memory to remember the things they need to do.
We need these modifications to make it Turing Complete:
- The world is a rectangular grid with width 2 that extends infinitely in one direction.
- The input of a Turing machine is given as a line of food in the first line that represents the tape, and a second line of empty tile with one critter on it.
- Some useless actions of critters (in this settings e.g. bud) are interpreted as a yes halt, some as a no halt, some simply as a halt. The rest actions are useful.
#
Turing Machine SimulationA Turing Machine is specified by an alphabet, a state set, and transition rules.
In a Turing machine, the alphabet is a set of all characters that can initially appear on the tape. In critter world, the alphabet is a set of all possible food valeus that can initially appear on the second line.
The state set can be represented by the finite amount of critter memory that you specify during critter creation. Note that we can also just use them as variables conveniently while still representing a Turing machine. It is explained in section 2.1 in Cornell's Turing Machine Handout.
The transition rules are simply a critter program which is just a big chunk of if-else block that encode transition rules.
Hence, critter world is Turing complete.
#
A Working ExampleI will demonstrate a very simple example, adding 1 to a binary number, ignoring overflow problems. We assume the number is given in little-endian format. (i.e. 2 is given as 01 instead of 10.)
Here is what you will do in Turing Machine pseudocode, which is very straight-forward:
However, critter world does not understand the JavaScript above. Since it's very tedious to dealing with those low-level critter world details (e.g. cannot do multiple actions in one step), I created a tool to try to compile a higher level non-Turing-complete language to a low-level language like critter language. The language disallows recursion and aggressively inlines variables and functions to put everything into a set of global variables and a single giant expression. The tool is called primitivize and is open sourced on GitHub.
Here is the code that will be compiled to a critter language:
The code already looks nasty somewhere, but the compiled code's readability is comparable to assembly. Here is a random segment of it:
The simulation appears to be pretty good!
(In the demo, the initial tape content is 1111101 and the expected output should be 0000011.)