What is a Turing Machine?

---

A Turing Machine is an idea that Alan Turing had for a machine that could solve any particular mathematical problem. He published his idea in a paper in 1936. Of course, he didn't call it a "Turing Machine" in his paper; that name stuck after other mathematicians just kept referring to it by that name.

---

The machine that Alan Turing described might look something like this:

It's just a box with a Read/Write Head sticking out of one side. A paper tape can be inserted into the Read/Write Head. The paper tape must be infinitely long and is divided into infinitely many squares (just like toilet paper, only stronger.)

The machine can move the paper tape through the Read/Write Head to the left or right, one square at a time. It can read the number or symbol on the tape. It can then erase the number or symbol that it sees, and write another number or symbol in its place, or just leave it unchanged.

---

The machine can be used in the following way:

Any data that the Turing Machine may require must first be written on the paper tape, with only one number or symbol per square. The tape is then inserted into the Read/Write Head. As the Turing Machine runs, it keeps moving the tape to the left or right, one square at a time, and all this time it's also reading the tape, erasing it, and writing to it. It may very well be using the paper tape for scratch paper, where it records intermediate computations for later use. When done, the answer will be on the paper tape.

---

As you can imagine, there are very many different Turing Machines; in fact, there are infinitely many of them. Each one does what it is intended to do, according to what's inside the box.

For example, you can have a Turing Machine that can read two numbers from the tape, add them together, and write the sum on the tape.

Or, you can have one that reads a number and writes its square root.

Or, you can have a Turing Machine that reads in two positive integers and computes the greatest common factor of those two numbers using the Euclidean Algorithm. In fact, the Excel File that you can download from this website has exactly that Turing Machine as one of its built-in examples. The name of this particular Turing Machine is EUC; it's the name given to it by Sir Roger Penrose in his book The Emperor's New Mind.

Just remember, that when providing your specific Turing Machine with data, that it's written on the tape in exactly the way the your Turing Machine expects it to be.