A (purely functional) Turing Machine simulator in Scala


While preparing for the exam for a Language Theory course I took, I have many exercises requiring to draw turing machines. Having to verify them manually is pretty cumbersome, so just for fun I set out to write one in Scala and stay in a pure functional style.

If you want a definition of a turing machine you can always go to wikipedia , but simplifying (a lot), you can see it as a finite state machine with a read/write head over an infinite tape.

The implementation

First we need to model the tape. We just need four operations: move left, move right, read, and write. Your typical functional immutable list is not the best for that, as there's no way to go back (left) and moving ahead (right) is O(n). Doing it with an array or double linked list is trivial but they're mutable, we're stuck!

If you think about it, we need to go step by step forward and change the head, for that the normal immutable list is perfect, but how we go back step by step?
Any idea?
What if we keep another list with the elements we'll find if we go backwards? Then, advancing thought the list is just a matter of taking the head of the forward list and adding as head of the backward list and vice-versa. As a plus, to add/update/remove we just change the head of the  forward list.
Does it make sense? Congratulations, we just reinvented/discovered the List Zipper ! (as usual, there's a nice explanation in "Learn you a Haskell..." )

A Zipper

Simple zipper implementation in Scala will look like:

The Tape

We're going to adapt the idea to model our tape with a couple of tweaks: first to better represent the concept of the read/write head in the tape, we're going to keep the element under focus separated form the list (actually is the same as working with the head of the list in the zipper, but when I started with the implementation I thought it could be easier to understand this way ). The important tweak is that the previous list zipper implementation works on a finite list, but our turing machine operates on an infinite list, so we need to adapt the left/right (or forward/back) operations to check when the list is empty and add a new blank element, so we never "fall off". So, our tape will look like:

To make things easier on notation, we can also define two vals holding the right and left functions:

The interpreter

Once the infinite tape is in place, the rest of the turing machine is easy: we need a state machine that based on the current symbol under the head and the current machine state, decides whether to write, move the head right or left and what's the next state. Using maps for those transitions is very straightforward: We use a map from the current state to a map from the current symbol

You can think of the transition as a function T: State x Symbol => (State, Symbol,Move)

Or in types:

With that, the core of our Turing Machine (the interpreter), is pretty simple:

We have q: the current state, t:the tape (and head), tm is the transition matrix and qf is the final state, because we need to know when to stop. If we're in the final state, we return the tape, if not, we look-up the state, symbol and move for  the current state and symbol on the head of the tape and recursively call step again with the new state, the result of writing the new symbol on the tape and the same transition matrix and final state. Because the call to step is the last function we call, we can optimize the recursive call with @tailrec.

An example

Here is an example, the turing machine I wanted to test is the following:
Given an imput string in the form bn#1^k , where bn is a binary representation of number n and 1^k are '1' repeated k times, we want to calculate the binary number bn+k . ( i.e. incrementing bn by k)

If we run the program, you'll see the expected results:


You can check the full code in github: https://gist.github.com/1258371

Well, that's all :)


There's an important conclusion to this: we implemented a Turing Machine in a purely functional way.
If we encode the Universal Turing machine in the transition table, we can feed the program itself on the tape. Because is purely functional, we can directly translate our program to lambda calculus, thus proving* that the lambda calculus is as powerful as a turning machine. If we come up with a lambda calculus implementation in a turing machine, you have the equivalence of the turing machine/lambda calculus models. Hint: implementing the lambda calculus interpreter in a turing machine is not far from what the Scala compiler and the JVM are doing in this case (or a Haskell interpreter for what is worth) 
*some handwaving required (or a lot), we're just fleas standing in the shoulder of gigants


Charles Houston said...

Nice post. I learn something more challenging on different blogs everyday. It will always be stimulating to read content from other writers and practice a little something from their store. I’d prefer to use some with the content on my blog whether you don’t mind. Naturally I’ll give you a link on your web blog. Thanks for sharing.

Unknown said...

Glad you liked them

RavenCSI said...

"Thanks for the wonderful content it is very helpful for us

RavenCSI is the only survey tool which provides real time alerts, easy to design dynamic dashboards, helps in importing files, mobile friendly survey tool.

suvery tool | free suvery tool | patient satisfaction survey"

Unknown said...

I am a constant reader of blogs. I have read this whole blog and it is an amazing blog for developers who are dealing daily with the new challenges and tasks.
Thank You for sharing such a valuable, informative and useful thoughts for users in your blog. app development company in bhopal
Top It companies in Bhopal
Companies in MPNagar Bhopal

Mounika said...

Nice explanations of the software development basics, it's good to know that! A friend of mine has implemented a company which is the ERP software in Hyderabad right now, she provides cloud based ERP software in Hyderabad, so I hope it goes well for her.
Best Regards

Yashika Jadon said...

This blog for software development are very informative! We find these technology-related topics very daunting, but for our projects we can now use these references. We really enjoy the blog which gives real examples, so that anyone can know. Great job! Great job! Keep it up.

online pet shop in delhi said...

Website Designing Company in Delhi, Ecommerce Website Designing Company in Delhi, Website Development Company in India, Website Designing Company in India, Ecommerce Website Designing Company in India, Website Design Company Delhi, Website Designing Agency, Website Design Company India, Ecommerce Website Designing Company India, Ecommerce Website Designing Company Delhi, Ecommerce Web Designing Company India, Ecommerce Web Designing Company Delhi, Ecommerce website designing company in India, Web development company in India, website development company in India,
itservice in india

Webcraft IT said...

Thanks for sharing such an interesting article with us. Best App Development Company in Indore