The Turing Machine and Computation

Thursday - May 4 2023, 04:43 UTC - 1 year ago

In 1936, Alan Turing wrote a seminal paper that provided a concrete answer to the question of what can be computed in the form of an abstract machine called the Turing machine. When given an input, Turing machines halt and accept or reject the input based on a table of rules and the symbols on a tape.

Computation is a familiar concept most of us understand intuitively. Take the function f(x) = x + 3. When x is three, f(3) = 3 + 3. Six. Easy. It seems obvious that this function is computable. But some functions aren’t so simple, and it’s not so easy to determine if they can be computed, meaning they may never give us a final answer.

In 1928, the German mathematicians David Hilbert and Wilhelm Ackermann proposed a question called the Entscheidungsproblem ("decision problem"). In time, their question would lead to a formal definition of computability, one that allowed mathematicians to answer a host of new problems and laid the foundation for theoretical computer science.

The definition came from a 23-year-old grad student named Alan Turing, who in 1936 wrote a seminal paper that not only formalized the concept of computation, but also proved a fundamental question in mathematics and created the intellectual foundation for the invention of the electronic computer. Turing’s great insight was to provide a concrete answer to the computation question in the form of an abstract machine, later named the Turing machine by his doctoral adviser, Alonzo Church. It’s abstract because it doesn’t (and can’t) physically exist as a tangible device. Instead, it’s a conceptual model of computation: If the machine can calculate a function, then the function is computable.

Here’s how it works. A Turing machine can read and alter symbols on an infinitely long tape, as dictated by a table of rules. The tape is made up of "cells," which can each store exactly one symbol, and the machine reads and rewrites the cells’ contents with a tape head. Each rule in the table determines what the machine should do based on both its current state and the symbol it’s reading. The machine can enter a final state ("accept state" or "reject state") upon which it halts, accepting or rejecting the input. Or it falls into an infinite loop and continues reading the tape forever.

The best way to understand a Turing machine is to consider a simple example. Let’s imagine one that’s designed to tell us whether a given input is the number zero. We’ll use the input number 0001 accompanied by blank symbols (#), so "#0001#" is the relevant part of our tape.

The machine starts in the initial state, which we’ll call q0. It reads the leftmost cell on our tape and finds a blank space. The rules say, "When in state q0, if the symbol is #, leave it as is without modification, move one cell to the right, and change the machine’s state to q1." After this step, the machine is in state q1, and its head is reading the second symbol, 0.

Now we look for a rule that applies to these conditions. We find one that says, "Remain in state q1 and move the head one cell to the right." This leaves us in the same position (in state q1, reading "0"), so we keep moving to the right until the head finally reads a different number, the 1.

When we consult the table again, we find a new rule: "If we encounter a 1, transition to q2, which is a ‘reject’ state." The machine stops, answering "No" to the original question, "Is ‘0001’ zero?" .

If instead the input is "#0000#," the machine will encounter a # after all those zeros. When we consult the table, we find a rule saying that this means the machine enters state q3, an "accept" state. Now the answer is "Yes," and the Turing machine terminates.