Universal Turing Machine in C#

I realized that this blog is fairly absent of any actual programming posts, even though it takes up a majority of my time on any given day (or night).

Here is a complete Universal Turing Machine I wrote in C#. The state table computes general relativity, based on my "theory of everything" down in another blog post. Each bit on the tape represents a photon and each full cycle represents a frame of reference.

I've excluded some code from my implementation so that it is easier to read, specifically if you run this, make sure you change the stopping criteria or run it in a console application in debug mode with a break point.

This is easily ported to JavaScript, so look forward to a jQuery plugin soon.

A paper where Turing first proposed the idea of computable numbers:

http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

  

// DIGITAL UNIVERSAL TURING MACHINE – C# 
// -------------------------------------
// Author: Kenny Bastani
//
// Based on the theory of computable numbers by Alan Turing
// Inspired by James Gleick’s “The Information: A History, a Theory, a Flood"
// 
// positions[] table is an infinite length: 
// ----------------------------------------
// positions[i] = (positions[i] >= tape.Length ? positions[i] % tape.Length : positions[i]) 
// OR 
// positions[i] = (positions[i] < 0 ? tape.Length – 1 : positions[i])
//
// STATE A:
//          0: move forward 1 space; state A
//          1: write 0; state B
// STATE B:
//          0: move forward 1 space; state C
//          1: move forward 1 space; state A
// STATE C:
//          0: stay; state B
//          1: move backward 1 space; state D
// STATE D:
//          0: write 1; state B
//          1: stay; state C

byte i = 0;
while (true)
{
    // The positions table stores the position of the Turing machine on the tape,
    // where byte i represents multiple Turing machines operating on the same tape
    byte bit = tape[positions[i]];
    switch (turingMachines[i])
    {
        // State A is the ready state, it holds no memory of erasing a bit. This is the "ZERO STATE".
        case "A":
            if (bit == 0)
            {
                // Advance until a bit 1 is found
                positions[i]++;
                turingMachines[i] = "A";
            }
            else if (bit == 1)
            {
                // Erase the bit from the tape and store it in memory as state B  
                tape[positions[i]] = 0;
                turingMachines[i] = "B";
            }
            break;
        case "B":
            if (bit == 0)
            {
                // Advance until a bit 1 is found
                positions[i]++;
                turingMachines[i] = "C";
            }
            else if (bit == 1)
            {
                // If a bit in state B is equal to 1, it is because the machine 
                // just wrote it to the tape
                positions[i]++;
                turingMachines[i] = "A";
            }
            break;
        case "C":
            if (bit == 0)
            {
                // A bit 1 is held in memory, switch to B state and continue oscillating
                // until colliding with bit 1
                turingMachines[i] = "B";
            }
            else if (bit == 1)
            {
                // A bit 1 has been found and cannot be erased because a bit is already 
                // in memory, move back one space and switch to the D state
                positions[i]--;
                turingMachines[i] = "D";
            }
            break;
        case "D":
            if (bit == 0)
            {
                // Release the bit from memory and write it back to the tape, 
                // revert to state B
                tape[positions[i]] = 1;
                turingMachines[i] = "B";
            }
            else if (bit == 1)
            {
                // This state is rare and happens when another Turing machine has released 
                // a bit in a parallel operation, revert to state C
                turingMachines[i] = "C";
            }
            break;
        default:
            break;
    }
}