CS and Game Theory

I read Papadimitriou’s article on Algorithms, Games, and the Internet, and found it to be a rather nice overview strongly hinting at future emphasis within the Theoretical Computer Science community. I’ve long thought that a good game theoretic background would…

Descriptive Hierarchies

Today, I was reading Sipser’s Theory of Computation and in chapter 6 it said: For statement 3 (Machines cannot self-reproduce) we make the following argument that machines cannot self-reproduce. Consider a machine that constructs other machines, such as an automated…

Universal Turing Machines, Part 9: Fin

The last routine left us with markings on the bits of the current state. Conveniently, it also left us to the left, while the UTM’s Start state has a loop which moves right to check wether or not a symbol…

Universal Turing Machines, Part 8: Lost in Transition

First: Last weekend I met with a friend and we reviewed this UTM subroutine by subroutine, finding a few errata, which have been fixed. Finally, we’ve reached the end. The last step of simulation is to find and mark the…

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…