June 2007
« May   Jul »




Universal Turing Machines, Part 7: Registration

Now it is time to determine the state that we will transition into. Because of the difficulty of matching a sequence of symbols (the little q) that is sitting in the middle of a list (the big Q‘s) we will first copy this symbol to the register.

Scanning left from the Tape marker, we can […]

The Microsoft Tax

I recently decide to purchase a Laptop. My concerns were: must be 64-bit, must be lightweight, should be tiny. Using the venerable pricegrabber, which lets you sort and filter by many aspects (and so beats froogle to a bloody pulp), I decided upon a factory refurbished AV4155-EH1 by Averatec.

The stats: Amd Turion 64 Mobile-30 […]

Universal Turing Machines, Part 6: Headbashing

Ok, so we just finished simulating a write, now it’s time to simulate movement of the head to the Left or Right one square. This routine should be fairly straightforward.

Scan back to the symbol in the transition table and read the L or R. Scan forward to the marked symbol on the tape. If […]

Universal Turing Machines, Part 5: She Puts the Symbol on the Tape

The last routine left us conveniently positioned on the s character of the symbol which is to be copied to the marked position on the simulated tape. The marked tape symbol is also fully marked up, so as we copy we will be unmarking its bits, while the symbol in the transition function is not […]

Universal Turing Machines, Part 4: Symbol Lookup

All right, so far we are assured that a marked symbol is on the simulated tape, and the machine head somewhere nearby. We will now have to find the appropriate transition rule in the encoded machine. We will loop through the possible transition functions until we find one that matches with the symbol on the […]

Universal Turing Machines, Part 3: Initialization

The first thing we do is scan the machines head all the way over to the Right end of the tape, stopping when we hit a s. If we accidentally scan too far and hit a , then we’ll have to scan back and copy the designated blank symbol onto the end of the tape, […]

Universal Turing Machines, Part 2: The encoding and overall design

The encoding for a machine with any number of states and any number of symbols:

Each state and each symbol will be numbered in binary, all the numbers must be padded to the same length. So, we can have symbols that number from 000 to 100, and states that number from 0010 to 1100.

Firstly, […]

Universal Turing Machines, Part 1: The Journey Begins.

This past weekend I spent some time working with Turing Machines. More specifically, I implemented a busy beaver machine. After that I worked on getting Ullman and Hopcroft’s UTM to simulate the machine that recognizes (01)* with input 010101.

I came no nearer understanding how Ullman and Hopcroft’s machine worked after a successful run, so […]

Workin’ for the Man

This last week, I showed what I’ve been working on for the last 7 months to my superior, only to be shot down. I’m responsible for ‘porting’ (really, it’s a complete rewrite) a Geospatial Information program from M$ windows to a custom in-house version of Linux. I modified the interface along the way, because I […]

Linguistic Engineering

I’m going to found the field of Linguistic Engineering. I wish to study the relationship between what people think (algorithms) and what they say (programs), with the end goal being a set of design principles for the creation of programming languages for specific problem domains (ex. parallel computation and quantum computation ). This subject has […]