How to Run a Turing Machine

Jun Aoyama on Flickr

A pen and paper computer that can do what computers do today.

You may have heard of Alan Turing, the British mathematician that helped crack the German Engima device during WWII and who invented our current notion of how to tell if an AI is conscious like a human, but his first major contribution to mathematics and computer science, long before we had computers, was the invention of the Turing machine.

Turing machines are simple devices that are made out of some kind of paper tape, a pen, and a way to read, write, or erase what’s on the paper tape. They also can solve any problem that a computer today can handle. While to Turing they were entirely hypothetical, some people have tried to make physical machines like the video linked at the bottom of the article.

Turing didn’t call them “Turing machines”, though; he called them “a-machines”. He introduced them in a paper in 1936. The paper has a bit of a nondescript title: On computable numbers, with an application to the entscheidungproblem. That name doesn’t necessarily mean anything to us, but it meant a lot to other mathematicians at the time. In those days, mathematicians were very concerned about the “entscheidungproblem”, the decision problem.

The decision problem was about whether machines could potentially make the lives of mathematicians easier. They wanted to know whether it was possible to give a machine a logical statement and for the machine to run a program and decide if it is always true.


Become a subscriber and get access to the rest of this article. Plus all our magazine articles.

Stories also include numerous links to help parents, kids, and teachers learn more. Get access today at just $15 per year!

Subscribe Today!

Also In The June 2017 Issue

Building and creating your tools with the Minecraft toolbox helps you survive the game.

Sensors give robots the senses humans have.

30+ ideas for all age holiday gifts, from books to apps to board games to VR and more.

There might be a reason that too-real robot and video game character creeps you out.

This programming language uses colors instead of text and punctuation to add and perform other tasks.

Knowing how passwords are cracked can help you create better passwords.

There are a number of strategies teachers (plus parents and students) can take to learn programming.

This project uses conductive thread to create a glove to activates your phone.

Software programming does neat things with language, in this case, mixing capital letters.

This Scratch game has lots of ways you can customize the game play. No cats were harmed in the making of this article either.

Links from the bottom of all the October 2017 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for October 2017.