4/6/12

A (purely functional) Turing Machine simulator in Scala

Why?

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:


10
100
1010
10000
11
100

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

Well, that's all :)

Conclusion

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

15 comments:

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,
Asiaitservices
itservice in india

Webcraft IT said...


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

High Technologies Solutions said...

High Technologies Solutions Provide Classroom and Online SAP Training and counseling organization giving SAP Training, SAP Courses, Online Sap Training and Certification.

World Best Training Center for SAP Training Course with 100% Placement assistance

Sap Training Institute in Delhi
Sap Training Institute in Noida
Sap Training Center in Delhi
Sap Training Center in Noida

Jones Brianna said...

This is an awesome blog that contains very valuable information. I am gonna bookmark this post. I really appreciate your work and happy to see your efforts towards blogging! Thank you, dear.
Sports Betting Software Development

💜💚💙 Sagar Leo Uppari (writer)✍ 💜💚💙 said...

It’s actually a great and helpful piece of information.
Thanks for sharing this useful article with us.
You can find more information click here software services in hyderabad

Mobzway said...

I have express a few of the articles on your website now, and I really like your style of blogging. I added it to my favorite’s blog site list and will be checking back soon… Visit: Poker Game Development Company

Legal Legends said...

A trademark renewal is required every 10 years. This 10 year period runs for the date that the trademark was initially filed.Unlike a patent, a trademark can be renewed every 10 years in perpetuity.Apply for trademark registration renewal online in South Africa at Legal Legends at affordable cost. File a renewal application for a trademark with your reliable partner now.

Alwin Co Daan said...

Great Article. Thank you for sharing! Really an awesome post for every one.

IEEE Final Year projects Project Centers in Chennai are consistently sought after. Final Year Students Projects take a shot at them to improve their aptitudes, while specialists like the enjoyment in interfering with innovation. For experts, it's an alternate ball game through and through. Smaller than expected IEEE Final Year project centers ground for all fragments of CSE & IT engineers hoping to assemble. Final Year Projects for CSE It gives you tips and rules that is progressively critical to consider while choosing any final year project point.

Spring Framework has already made serious inroads as an integrated technology stack for building user-facing applications. Spring Framework Corporate TRaining the authors explore the idea of using Java in Big Data platforms.
Specifically, Spring Framework provides various tasks are geared around preparing data for further analysis and visualization. Spring Training in Chennai


The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

Angelina said...

I have learnt a lot about phantom types in Java. However, IT companies can leverage the benefits of software development outsourcing to adopt agile methodologies for product development & deployment.