The Interruptable Power Supply
I usally goto my grandmother’s house for dinner, and today was no exception. On my home machine I’m busy compiling kde as part of a gentoo installation in a chroot on the hard drive I took out of my new…
FedEx Sux
Alright, so I ordered a laptop, and the supplier chose to ship FedEx, I chose Ground (because I’m cheap). So, Thursday morning, before work, I check up on the tracking number, and the FedEx website says it was in L.A….
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…
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),…
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…
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…
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…
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…
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…
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…