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…
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…
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…
The Rules of Logic
Taken from Scott Aaronson’s PHYS771 Quantum Computing Since Democritus Propositional Tautologies: A or not A, not(A and not A), etc. are valid. Modus Ponens: If A is valid and A implies B is valid then B is valid. Equality Rules:…
Bureaucracy 2.0
buzzword: Achieving higher levels of inefficiency through the inappropriate application of technology. I was sitting in a meeting yesterday, and realized that the conventional approach to software design (more generally, any big project) is for upper management think that they…