How a Turing Machine works

For years I struggled to clarify exactly what a Turing machine needs to do, and more importantly, how Turing conceived of it. Even after I finished a CS degree I wasn’t able to “build one from scratch” because I hadn’t yet independently realized what he had…

09484-1jm-kt25lww9sh33epb8ctw

Recently I had a moment of insight and hit on an improved analogy for the “program” of a Turing machine, which Turing describes as “a book”. I took this one step further and clarified that each page in this book can be thought of as a unique state. A page contains a single instruction to follow (which takes the form of a conditional statement). This subtle step is something Turing didn’t include in his paper (instead he skipped ahead and simply refers to it as a ‘big table’, which can be tough to digest at first)

Screen Shot 2017-05-17 at 2.31.03 PM

I feel this is the key to make the mechanism behind Turing machines more concrete and intuitive for the new learner. I hope Turing would approve of my modification to his analogy…and after reading his paper some 20 times, I can say with certainty that he would.

Here is the video on how it all works (this is also the 2nd last video in the CS series)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: