Turing Machines and the Limits of Computers

What are Turing machines, and why are they so important?

Imagine it is the year 1936. “Pennies from Heaven” by Bing Crosby is the biggest hit of the year and prohibition ended just three years ago in the United States. It will be another 40 years until the Apple I (Apple’s first computer) is produced. In this pre-digital time before Amazon has figured out same-day delivery, Alan Turing has presented his idea of the “Turing machine,” and the wheels have been set in motion for our modern computerized world.

If you are new to theory of computation concepts and want a high level view of Turing machines, keep on reading! For a more in-depth look, see the book I referenced at the bottom of this article.

What is a Turing machine?

A Turing machine is a theoretical model of a computer with two components: an infinitely long memory tape and a read/write tape head. Each unit of memory on the tape holds a symbol (such as 1,0,a,#,$, etc.). Below is a basic representation:

Turing machines in action

To get a better understanding of Turing machines, let’s write a basic program for one. This can be done informally by using psuedocode.

Imagine we want to determine if a given string of characters has an even length. Given a string like “abc”, we would “reject,” meaning the length isn’t even. Given a string like “aa”, we would “accept,” meaning the length is even.

Here is the pseudocode for this Turing machine:

1. On input W do:
2. Let isEven = true
3. For each character C in W, let isEven= !isEven (if isEven is true, make it false, and if false, make it true)
4. If isEven is true, accept. Otherwise, reject.

On line 1, we accept some string and represent it as “W”. Then on line 2, we initialize a value we call “isEven” which starts out with the value “true”, and on line 3 toggles between values “true” and “false” for each character in “W”. Finally on line 4, we “accept” if our “isEven” value ended up with the value “true”, and “reject” otherwise.

We can also think of this using the representation of a Turing machine as a memory tape and a read/write tape head mentioned above. If we were given an input “abcd,” our tape may initially look like this:

a b c d 1…

The first four characters are our input and the last one represents our “isEven” value. We will use “0” for false and “1” for true. The “…” indicates that our memory tape extends into infinity. The remaining steps of the program would be this:

a b c d 0… (Read character ‘a’. set isEven to false)

a b c d 1… (Read character ‘b’. set isEven to true)

a b c d 0… (Read character ‘c’. set isEven to false)

a b c d 1… (Read character ‘d’. set isEven to true)

We ended with “isEven” set to true, so our machine would accept!

What can a Turing machine do?

This simple theoretical device can solve any problem that an existing computer or any future computer can solve. In fact, if a proof can be written to show that a certain problem is unsolvable by a Turing machine, we know that a real computer would never be able to solve that problem.

For example, we know from proofs using Turing machines that software cannot be written to determine if another piece of software will enter an infinite loop (this is called the “halting problem”) or determine if two pieces of software produce identical results.

Why are Turing machines so important?

The genius of Alan Turing and his Turing machine concept is that he was able to prove the limits of computers before they existed. Knowing these limitations, we know what programs are impossible to create, and adjust accordingly.

Since we know from proofs using Turing machines that we can’t detect if a program will enter an infinite loop, software developers don’t spend time and resources solving this. To get around this, software developers instead set a time limit for a program to run where it should reasonably be able to complete, and if it exceeds that time, it terminates and assumes there must have been an infinite loop.

Similarly, no software developer who is informed on computation theory would attempt to write a program to ensure that whenever they update their code, no new bugs are introduced and their old and new code produce the same exact results. Instead, they write tests that validate the correctness of code for specific inputs and rely on writing good and complete sets of tests.

Thanks to Turing machines, we know what is and isn’t possible with computers!

Sipser, Michael. Introduction to the Theory of Competition. New York, Brooks Cole, 2005.