Turing Machine

December 2012An interactive Turing machine simulator and primer on computability

Theoretical basics

Theoretical computer science shed light on the notion of “solving problems algorithmically” or “computing functions algorithmically.” The pivotal insight being: You can boost the calculation speed of a computer but not its capabilities. That is, a super computer is faster than your personal computer, which is faster than your smartphone, which is faster than the microcontroller in your washing machine. But all these devices can — given enough working memory — compute the same functions. Such machines, which can (in principle) compute any function that is regarded “computable”, are called Turing-complete (more precisely, Turing completeness is the property of a set of manipulation rules applicable by such a machine). Turing machines are an abstract way of thinking about such “universal computing machines.”

I am going to adopt the notation used on the English Wikipedia (with slight modifications) since most readers unfamiliar with the concept of Turing machines might use this article as a starting point.

Well, what is a Turing machine? A Turing machine $\mathcal{M}$ is a 7-tuple

$$\mathcal{M}=\left(Q,\Sigma,\Gamma,F,q_0,\square,\delta\right)\,.$$

These seven elements describe the entire machine. How it starts, what it does, and how it stops (if it stops at all):

Turing machine

A Turing machine is the 7-tuple $\mathcal{M}=\left(Q,\Sigma,\Gamma,F,q_0,\square,\delta\right)$ where …

$Q$ is a finite, non-empty set of states.
$\Gamma$ is a finite, non-empty set of the tape alphabet/symbols.
$\square \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation).
$\Sigma\subseteq\Gamma\setminus\{\square\}$ is the set of input symbols.
$q_0 \in Q$ is the initial state.
$F \subseteq Q$ is the set of final or accepting states.
$\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R,N\}$ is a partial function called the transition function, where L is left shift, R is right shift and N is no shift.
Mathematically speaking: $\delta$ is a functional relation
$$\delta\,\subseteq\,\left(Q\setminus F\times\Gamma\right)\times\left(Q\times\Gamma\times\{L,R,N\}\right)\,.$$

For explanatory purposes a tape and a head are added as building blocks. The tape contains characters in $\Gamma$ and is basically the memory of the machine (since the tape is infinitely extended in both directions, the usable memory of a TM is unbounded). The head can read and write a single character on the tape at its current position. Furthermore, it can be shifted one character to the left/right per step and thus can be used to transform the data stored on the tape.

The general mode of operation is as follows:

A finite sequence of input symbols (a word) $w_0\in\Sigma^\ast$ is written on the tape. By convention, the head points to the leftmost character of the input. All other fields of the tape are initialized with the blank symbol $\square$.
The internal state of the TM is set to $q_0$, the initial state.
Now the TM starts to perform its computation, that is, its transformation of the input sequence $w_0$. This is done step by step. In each step, the transition relation $\delta$ is used to determine the next state, the symbol to write on the tape at the head’s position, and the head’s movement.
For example, let $\mathcal{M}$ be in the state $q\in Q\setminus F$ and the character on the tape at the head’s position reads $a\in\Gamma$. Provided the relation $\delta$ contains the element $\left(\left(q,a\right),\left(p,b,L\right)\right)$ the TM will switch to the internal state $p$, the head overwrites the $a$ with $b$, and finally the head moves one character to the left.
As long as the current state is not a final state, that is $q\notin F$, the machine performs the last step over and over again.
Note that $\delta$ is a functional relation but not necessarily a function (i.e., it is a partial function). Therefore it can happen that there is no transition defined for the current state and symbol at the head’s position. Then we say that the TM stops. If the current state is a final state, that is $q\in F$, we say that the TM halts.
Given the TM halted. Then the output $w_1\in\Gamma^\ast$ is written on the tape. (Note that there are always leftmost and rightmost non-blank characters which define the output string $w_1\in\Gamma^\ast$.)

Be aware that there are various conventions in the literature regarding the structure and the mode of operation of Turing machines. All these concepts are computationally equivalent and for some problems other conventions may be more convenient.

To conclude this section, I want to point out the possible outcomes once you started a TM with an input $w_0$:

After a finite number of steps, the TM ends up in a final state and halts. Then we say that $\mathcal{M}$ accepts $w_0$.
After a finite number of steps, the TM ends up in a non-final state where $\delta$ is undefined and stops. Then we say that $\mathcal{M}$ does not accept $w_0$.
The TM never stops and performs computations ad infinitum. Then we also say that $\mathcal{M}$ does not accept $w_0$.

The set (or language) of all accepted words $w_0\in\Sigma^\ast$ is denoted by $L\left(\mathcal{M}\right)\subseteq \Sigma^\ast$ and called the accepted language of $\mathcal{M}$. Such languages — that are accepted by some Turing machine — are called recursively enumerable. By the way, these are exactly the famous Type-0 languages in the Chomsky hierarchy.

Philosophical aspects

Ok. Now you know how a Turing machine works. But why the hell should you care about TMs anyway? Well, theoretical computer scientists’ creativity gave rise to a variety of (quite different) calculi to model the notion of “computing functions algorithmically” in an abstract way (e.g., the famous Lambda calculus). Some of these calculi were more powerful than others (i.e., they could compute more functions). But most of them were computationally equivalent to the concept of Turing machines — and there was no model which was more powerful. In other words: It seemed (and to this day is) impossible to contrive an abstract model of a computer which is more powerful (i.e., computes more functions) than a Turing machine! This insight led to the famous …

One could call this the “fundamental theorem of computability theory” if there was not a severe drawback: It reads “hypothesis”, not “theorem”. And with good reason! What is “intuitively computable” supposed to mean? Probably you have an intuitive notion of its meaning. The Church-Turing Hypothesis states that every function which can be computed somehow algorithmically, can be computed by a Turing machine. But since “intuitively computable” is not mathematically defined, there is no way you could prove this statement.

Nevertheless it is kind of a “working hypothesis” for theoretical computer scientists. No theorem proved within a certain (mathematically rigorous) framework would fail if the Church-Turing hypothesis fails. But some of them probably were “less important”, for a whole new world of computability would unfold.

When I first heard a computer scientist talking about the Church-Turing hypothesis, I got the impression that he was quite satisfied with the situation. Well, why not! The Church-Turing hypothesis constitutes a seemingly impenetrable foundation which grants computability theory practical impact. It somehow links the abstract field of computability theory to the real world while being unprovable from computability theory itself (Whew! Less work for us…). You probably already guessed where this journey ends: The Church-Turing hypothesis may be a footing — but there is a basement beneath; and there physics resides:

True! And this is the reason why physicists should be interested in computability theory (and it explains why there is a Turing machine simulator on a theoretical physicist’s website 😀). Equipped with this notion of computation being an inherently physical process, we may try to reformulate the Church-Turing hypothesis as follows:

That is, we replaced “intuitively computable” by “computable by a finitely realizable physical system.” This transformation is kind of naive and cries for a definition of “computable by a finitely realizable physical system” — but this is not the point (at least at this stage). The point is: This may be a hypothesis, but it is a physical one! And physical statements can be scrutinized by experiments, at least in principle. One cannot prove a physical statement true but one could disprove it by the realization of a physical system which computes a function which is known to be uncomputable on a Turing machine. (And there is no reason whatsoever that such a system cannot exist.)

As a last point, I want to draw your attention to the fact that the physical approach might yield a proof for the Church-Turing hypothesis within the formal framework of a physical theory. Then one will inevitably face the question what a “physical theory” actually is and how predictions about physical systems are computed by means of a theory. And when a strange loop arises, things get interesting …

Instructions

The turing machine simulator in the browser.

This is a simple simulator for a deterministic Turing machine

$$\mathcal{M}=\left(Q,\Sigma,\Gamma,F,q_0,\square,\delta\right)$$

written in vanilla JavaScript and HTML. It is not designed to be a fast and efficient simulator. My goal was to design a simulator for didactic purposes which implements the theory rigorously.

The simulator is not foolproof! If the transition relation is not functional (i.e., right-unique), the first applicable rule in the list will be used. That is, if your transition relation describes a non-deterministic Turing machine, the simulator will neither cast an error nor will the simulation live up to your expectations 😉.
Load an example and try to understand what happens. For example, choose “Unary addition” from the drop down menu and click “Load”. Note that the Parameters I are determined automatically and the input alphabet $\Sigma$ is set to $\Sigma=\lbrace\text{a},\text{\#}\rbrace$. Set $w_0$ to aaa#aa and click “Load parameters” (i.e., we want to compute $3+2$). Note that $w_0$ is a sequence of characters in $\Sigma$, formally: $w_0\in\Sigma^\ast$. By clicking “Load parameters” you wrote $w_0$ on the tape with the head on the first character. You may now click “Next step” to perform a single step or you run the machine automatically via “Start”. The computation has finished when $q\in F$, that is, when the machine ends up in the state “halt”. Then there should be $3+2=5$ $a$’s on the tape.