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

60 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"





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

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.

Sneha 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.

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.

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.

IIFL MULTISPHERE Consultancy said...

Hi, I have read your blog and found it very useful. Thanks for sharing such an interesting article with us. Keep Sharing.

Find the best Stock Broker in Gorakhpur
Mutual Funds in Gorakhpur

Babit said...

Thank you for sharing an interesting and very useful article. I believe this is useful. Thank you.
Software Development in Noida

Engineers India Research Institute said...

interesting article.


web development company in Indore

Membroz said...

Thanks to share this useful information, we happy to develop the trial of free workshop management software

daisoftware said...

This was a very meaningful post, so informative and encouraging information, Thank you for this post.
meal-kit delivery service

Unknown said...

Great information, Thanks for sharing.
Bangla News Paper 71
Web Design & Development in Dhaka

Milne said...

Software Development in Dubai
https://www.nsreem.com/ourservices/software-development/
NSREEM develop amazing desktop and web applications that are tailored to your specific requirements.
NSREEM is #1 in Software Development in Dubai
1633750677889-11

NKU Technologies said...

NKU Technologies connects your ecosystem from end-to-end, providing the glue that can make your enterprise stronger and more efficient than before.

Mobile Application Development Service
Web Application Development Sevice

Golden Eagle It Technologies said...

Thanks for sharing, this help me a lot in project as well

Writers said...

Nice work, truly valuable to me.
I hope you keep it up.
We are offering best offshore development services,
Visit here:
Iyrix Technologies
Remote Software Developers
Software Development Services
Data Visualization tools Developers
Mobile Application Development
Check Developers Rates

WNSUAE said...

Great! You have share your interesting ideas to us: Click for IT Solutions

it solutions company
it infrastructure consulting services
dubai cctv company
ip pbx dubai
dubai web developer
software development company uae
mobile app development company in dubai
email marketing dubai
White Star Net Solutions
WNSUAE

inwizards said...

Thank you for sharing this amazing blog post.
Hire Wordpress Developers
wordPress Development Company




Software Development Outsourcing said...

Thanks for sharing such a useful chunk of nice information.
Software Development Outsourcing

go2geeks said...

Thanks for sharing. Your blog is more informative. This is very nice article and very good information. We really enjoy your blog & content.
geeks to you melbourne

Aarya Sharma said...

Thanks for sharing this amazing content. I learn new information from your article, I am really happy to say it’s an amazing post to read. you are doing a great job. Keep it up.

Fantasy Sports App Development

Anonymous said...

We strategize, design, and build best-in-class digital products, transform teams, and co-create
disruptive business models. We work as technology innovation Web Application Development Services partners with our clients, helping them adapt and thrive in the digital era

Anonymous said...

Thanks for sharing an interesting post. Contact us for Software Development Services DevBatch

Anonymous said...

Thanks for sharing an interesting post. Contact to Custom Software Development Services Company

Shams Malik said...

A debt of gratitude is in order for sharing awesome Information. In this article I glean some significant experience. What's more, to know m about wedding or marital administrations visit

Data Science Services

Dhamaal Games said...

Thanks for sharing such an interesting article! your post is very informative and valuable. visit: Dhamaal Games

Online Accounting Consultant in India said...

GST & IT Buddies is aonline accounting consultant company with experience in Accounting, Taxation & Registration, that also caters to all other financial requirements. We have helped over 5000+ clients with their tax filing processes and are still counting, along with providing consultation to small, mid and high-level companies. Visit us for more info: http://www.gstnitbuddies.com/

GST Registration Consultants said...

Are you searching for GST registration consultant in India? Contact us today for all services related to GST Registration, GST Filing, GST E-Way Bill, and many more.

Software Development Outsourcing said...

Thanks for sharing such information it will help out different software developers to learn more and grow.

Golden Eagle It Technologies said...

This is mind blowing, thanks for sharing this informative content

RoyexMetaverse said...

Very useful article. Thanks for sharing such an informative & useful article with us.

Metaverse Development Company in Dubai

Neha said...

Are you looking for an Agarbatti manufacturer in India?NarainUdyog is a leading manufacturer and supplier of the finest quality products.

intellimindz said...

SolidWorks Training in Chennai|
SolidWorks Training in Chennai|
Ansys Training in Chennai

shivani roy said...

Thanks for sharing useful information. Please contact us for Ecommerce website packages India.

shivani roy said...

This was a fantastic blog. A lot of very good information given,

Website designing company in Noida. Please contact us for more details.

ready to wear dresses said...

Great post, Lot's of useful information. Keep up the good work and keep posting to others!

water air cooler said...

Very nice and informational blog.

roohi said...

If you are looking for SSL certificate email address for your business then please contact us for more information.

Rejuvenation fitness said...

Rejuvenation Fitness Group is India's no. 1fitness training program that provides fitness trainer in delhi.please contact us for more info.

Growth leader said...

If you are looking for web designing company in delhi for your business then please contact us for more information.

Growth leader said...

Find a leading digital marketing agency in Delhi for strategic online solutions, SEO, social media, and more. Elevate your brand.please contact us.

Bhola online said...

Choose a reliable betting ID provider for a seamless wagering experience. Trust us for top-notch odds and secure transactions.

Manisha Sharma said...

Amazing article

Fantasy Sports App Development Company