Universal Turing Machines, Part 1: The Journey Begins.

2007/06/19 · by · in Comp*

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 I’ve decided to design my own. I’m also going to fix up the UTM encoding so that it’ll be easier to generate the input, and so that it’ll naturally simulate machines with an arbitrary number of states and tape symbols.

a Busy Beaver machine: code output
TM for (01)*: code output
Ullman and Hopcroft’s UTM: code output