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

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.

Web development company in UK | Cubestech said...

Thanks for sharing such an interesting article. As a trainee working as a software developer at(cubestech). This blog would be very useful for our projects and future references. keep on updating.

Python Training Expert said...

Lean Python Training Core to Advance Level with Your Comfortable Time. Further More Information Contact Here-+91-9310332343 Or Visit Website- http://www.pythontrainingdelhi.com/

Edithtech Infrastructure Private Limited said...

Call @ +91 9907119079. Whether you require a web development company in Indore or an app development company in Indore for a shop, beauty salon, gym, hotel, small business. We are here to provide easily customizable solutions for your requirements, by keeping things simple for you and advise you for your best suitable option as per your requirement which will help you in growing your business.

Vai Vai Cleaning said...

We are offering you commercial cleaning services. Whether you have a small or big corporate office or home, if you are conscious about their deep cleaning, “Vai Vai cleaning” is here to help you. We provide restaurants, industrial cleaning services, or even your office and house cleaning services at a reasonable cost. We are experts in all sorts of cleaning, especially floor, glass, carpet, sofa, and kitchen.

Vai Vai Cleaning

Techsaga Corporations said...
This comment has been removed by the author.
Techsaga Corporations said...

At Techsaga corporations, it serves you with end-to-end Indian business consultancies and development solutions. We help you plan, conceive, incorporate, build, augment, and take care of your software with the help of our industry experts from different knowledge domains – offering you absolute benefits from our expert consulting.

Raj Sharma said...

Web Development Training Course in Noida

emailtaai said...

Software development company in Noida team has to perform in accord with the client's engineering team for ideal results. Techsaga Corporations address this facet of the software development process most aggressively with our streamlined and well-planned resources.

Unknown said...

Techsaga, as Software development company experts, deliver inspiring, eye-catching designs and measurable campaigns that connect with target audiences, boost online marketing and encourage business growth. We can help you meet your needs across a range of full service online marketing services. Are you looking for help with great content, SEO, PPC campaigns, a full digital marketing strategy, campaign, or something else? No matter what you need, our experts can help you.

Jimmy Noor said...

Nice blog, very nice information you have shared. Best APP developers offer custom android app development and software development service in Harrogate. Hire software mobile & app developers today!
app developers Harrogate

Ricky Liame said...

Nice blog, very nice information you have shared. The best software development company offers professional software development & mobile app development service in Yorkshire. Hire mobile & software developer today!
custom software development Yorkshire

Sera Doctor said...

seradoctor.com is an online-based medical services website. The goal of seradoctor.com is to establish an easy link for all people in the country to seek the advice of doctors who specialize in any physical problem.

Sera Doctor

Anyone can open a free account at seradoctor.com and give serials to all types of specialist doctors in just 1 minute. Also through seradoctor.com, you can easily find information on all groups of blood including all hospitals and clinics and diagnostic centers and all AC and non-AC ambulance information, contact address, and phone number very easily.