Saturday, July 19, 2014

Simple Python Turing machine implementation

I've always been a fan of using problem-solving to learn, over the years I've found it far more effective that rote learning or being lectured. Recently I came across this interesting implementation of a Turing machine. I'd obviously heard of Turing machines but I had never sat down and thought about how to "build" one.

Feeling inspired I cooked up this fairly simple Python example of a Turing machine*, using a rule set that counts up in binary on the "tape": This example counts up to 64 in Binary, printing out the tape each time the head resets to the start position.

* In this case, the "infinite tape" is only infinite for values of infinity less than the roughly 3 GB of free RAM that my laptop had at the time :)