beanz Magazine

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

Can we measure the time and steps required for things to happen?

This Canadian experiment used a robot to explore how people respond to robots and technology.

An amazing new book turns math problems into shapes and illustrations.

This pen and paper project helps organize ideas into stories with a finite state machine.

While you can't use soap and water on your code, you can keep your code as sparkly clean as any dish or silverware.

This project explores the basics of using Google's Static Map software to display your own maps.

Most people love cookies. But these cookies are the kind that make the internet possible.

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

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

Software languages don't magically appear. They're created by design. First in a series.