Hierarchical Pattern Recognition

About a year ago I read about Ray Kurzweil's "Pattern Recognition Theory of Mind", which he articulates in his book, "How to Create a Mind". I picked up the book after struggling with the idea of implementing a deep learning algorithm for parsing natural language text on Wikipedia. My goal was to discover links in volumes of text that were not already linked. I ended up developing all kinds of cool heuristics to do this, mostly by a lot of trial and error. King of these heuristics was a pretty simple algorithm at the core of the library that would find redundancies in batches of text content. 

How this worked is if a phrase was mentioned repeatedly in a collection of about 50 sentences, then I could extract that phrase as a node and link it back to the pieces of content it belonged to. Every now and then you'll get a reference to another article's name, which can then be verified against Wikipedia's site index, which would provide more sentences to find repeated phrases within.

I struggled with persistency because I knew how ugly my problem was for a relational database. I created some entity-relationship models, and implemented them using Entity Framework over Microsoft SQL Server. It worked, kind of. I waited patiently to happen upon a better solution. Thankfully I did, and using a graph database I was able to take my cool little algorithms and solve my persistency problem at scale.

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;
    }
}