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…
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….
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…
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),…
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…
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…
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 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…
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…
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…