3. Decidable Languages

In the last lecture, we have completed our formalization of the central question of the class. Our original question, What problems can computers solve?, has now been made precise. It corresponds to the question:

Which languages are decidable?

Or, to be more precise, I claim that this is the appropriate formalization of the original question. Let’s examine the class of decidable languages in a bit more detail to see if we believe that it does correspond to the intuitive notion of computability that we want it to capture.

Some Decidable Languages

Let’s begin by studying a few simple languages that our intuition suggest should definitely be computable and see if they are indeed decidable.

For a string $x = x_1 x_2 \cdots x_n$, denote its reversal by $x^R = x_n x_{n-1} \cdots x_1$.

Proposition 1. The palindrome language $\mathsf{PAL} = \big\{ x \in \{0,1\}^* : x = x^R \big\}$ is decidable.

Proof.

We can design a Turing machine that decides $\mathsf{PAL}$ in the following way:

Let $n$ denote the length of the input $x$.

If $n = 0$ or $n = 1$, then accept.

If $x_1 \neq x_n$, then reject.

Erase $x_1$ and $x_n$.

Go back to the first instruction on the remaining string $x' = x_2 x_3 \cdots x_{n-1}$.

(This construction can be made formal by giving an explicit transition diagram for this Turing machine, but this is left as an exercise.)

For the analysis, we need to argue that the Turing machine accepts every palindrome and rejects every string that is not a palindrome.

Correctness: For the palindromes, we can argue by induction on the length of $x$. In the base cases, the empty string and both strings of length 1 are palindromes and are correctly accepted by the algorithm. And for the induction step: Every string $x \in \mathsf{PAL}$ of length $n \ge 2$ satisfies $x_1 = x_n$ so the algorithm accepts it if and only if it accepts the string $x' = x_2 x_3 \cdots x_{n-1}$. But the string $x'$ is a palindrome of length $n-2$, and so by induction the Turing machine accepts $x'$.

Soundness: A string $x$ is not a palindrome if we can write $x = z0y1z^R$ or $x = z1y0z^R$ for some strings $y,z \in \{0,1\}^*$. In either case, the Turing machine will remove the first and last characters of the string until it reaches the string $0y1$ or $1y0$; in both of these cases, it then correctly rejects.

The palindrome language is context-free. We can also easily see that some non-context-free languages are decidable:

Proposition 2. The language $L = \big\{ 0^n1^n0^n : n \ge 0 \big\}$ is decidable.

Proof sketch.

We again design a Turing machine to decide the language. There are many ways that we can do this. One elegant method is to consider the tape alphabet $\{\square, 0, 1, X\}$. (Formally, the tape alphabet is $\Gamma = \{\square, 0, 1, 2\}$ but here and in many other settings it is much more convenient to use different symbols when giving the high-level description of a Turing machine.)

The Turing machine we construct proceeds in two stages. In the first stage, the machine accepts if the input is the empty string and otherwise rejects if the string is not of the form $0^k1^\ell0^m$ for some possibly distinct $k, \ell, m \ge 1$. And in the second stage, it iteratively replaces the first symbol of each block with an $X$. For example, on input $000111000$, it rewrites the input as $X00X11X00$, and then repeats the process to produce $XX0XX1XX0$. It continues this iterative process until either the whole string has been crossed off (in which case it accepts) or it can’t successfully complete the operation because at least one but not all of the blocks have been entirely crossed off (in which case it rejects).

Church-Turing Thesis

We could continue constructing Turing machines for more individual languages, but instead let us now examine the claim that Turing machines are general enough to capture the notion of what is computable by all other reasonable models of computation. The claim itself is known as the Church-Turing Thesis.

Church-Turing Thesis. Any decision problem that can be solved by any (reasonable) model of computer corresponds to a language that can be decided by a Turing machine.

We can’t prove the Church-Turing thesis, but we can certainly test it out with any reasonable model of computation that we can imagine. Here’s one such test.

A counter machine is a machine that has $k$ registers (for some finite $k \ge 1$) that each hold an integer. Importantly, the integers in these counters (unlike the ones in the computers we usually work with) are unbounded. The input to the counter machine is the binary representation of the number stored in the first register when it starts; all other registers initially hold the value $0$. A counter machine program is a finite list of operations from the following list:

$\texttt{CLR}(r)$ clears register $r$ by setting it to $0$.
$\texttt{INC}(r)$ increments the integer in register $r$.
$\texttt{DEC}(r)$ decrements register $r$.
$\texttt{CPY}(r,s)$ copies register $r$ into register $s$.
$\texttt{JMP}(a)$ jumps to the $a$th instruction in the program.
$\texttt{JZ}(a,r)$ jumps to the $a$th instruction if register $r$ equals zero.
$\texttt{HALT}$ halts the execution of the program.

A counter machine program computes the language $L \subseteq \{0,1\}^*$ when it halts on all inputs and has a non-zero value in register $1$ upon halting if and only if its input was in $L$.

As you can verify directly, counter machines can compute many non-trivial languages. (In fact, though we will not prove it, they can compute all decidable languages.) But using the same ideas as we used in the design of the Universal Turing Machine, we can show that all of the languages that can be computed by counter machines are indeed also computable by Turing machines.

Proposition 3. Every language $L \subseteq \{0,1\}^*$ that can be computed using counter machines can also be decided by a Turing machine.

Proof sketch.

The idea is that given the description of a counter program, we can design a Turing machine that simulates the program.

Fix a counter machine program $P$. We can initialize our simulation of $P$ on some input $x$ by writing the binary representation of $k$ integers on tape: the input $x$ itself is in the first stored register, and the other $k-1$ ones are initialized to $0$. We also add another counter on the tape to keep track of the current step of the program we are executing. We then simulate the execution of $P$ step by step.

Each $\texttt{CLR}$, $\texttt{INC}$, $\texttt{DEC}$, and $\texttt{CPY}$ operation can be implemented by modifying the appropriate register value on the tape directly. The $\texttt{JMP}$ operation is simulated by changing the value of the counter that keeps track of our current step in the execution of the program. And the $\texttt{JZ}$ operation is very similar, except that we add an extra check on the appropriate register and skip the jump if that register does not hold a zero.

Finally, when the counter machine program $\texttt{HALT}$s, we terminate the simulation, check the value in the first register stored on tape. We accept if that value is non-zero and reject otherwise.

The proof of the proposition gives the template for confirming the Church-Turing thesis on any other model of computation that you could define: to prove that Turing machines capture that model of computation, it suffices to show how to simulate the programs on these computers using a Turing machine.

Incidentally, you can use the same approach to show that any other model of computation is as powerful as Turing machines (and so, by the Church-Turing thesis, as powerful as any other reasonable model of computation!): simply show how Turing machines can be simulated in your model. Every model of computation for which this task can be completed is called Turing-complete.

Universal Turing Machine

One powerful idea that we introduced in the proof of the last proposition is that a single Turing machine can simulate any counter program $P$ if it is provided with the code for $P$. Perhaps the most far-reaching consequence of this powerful idea, first established by Alan Turing himself, is that there is a Universal Turing Machine that can simulate all other Turing machines. To properly introduce the Universal Turing Machine, we start with a basic observation.

Proposition 4. There is an encoding that maps each Turing machine $M$ to a binary string $\left< M \right> \in \{0,1\}^*$.

Proof.

The proposition is an immediate consequence of the fact that Turing machines have a finite description.

Or we can describe an explicit encoding in the following way. Consider the machine $M = (m,k,\delta)$. The positive integers $m$ and $k$ can be encoded by taking their binary representation. And the transition function $\delta$ can be represented as a table of $m \cdot (k+2)$ entries (one for each internal state-tape symbol pair). Each of these entries can be encoded as a binary string. We can combine all these elements into a single binary representation to obtain the final encoding of $M$.

We say that a Turing machine $S$ simulates machine $M$ on input $x \in \{0,1\}^*$ when $S$ accepts if and only if $M$ accepts $x$, $S$ rejects if and only if $M$ rejects $x$, and in both cases $S$ ends with the same content on the tape as $M$ does.

We can now show that there exists a single Turing machine that can simulate all the other ones in the following precise sense.

Universal TM Theorem. There is a Turing machine $U$ such that for every Turing machine $M$ and every input $x \in \{0,1\}^n$, when the input to $U$ is the string $\left< M \right> x$, then $U$ simulates the execution of $M$ on input $x$.

Proof.

We once again give only a high-level description of $U$.

As a first step, the machine $U$ turns the input $x$ into the initial configuration of $M$ by adding a special symbol $\mathbf{1}$ at the beginning of $x$ to turn it into the string $\mathbf{1}x$. Then it proceeds to simulate the execution of $M$ step by step. Each computational step is simulated by following a 3-stage process.

Read the current state $\mathbf{q}$ and the symbol $a$ at the tape head in $M$’s current configuration.

Go back to the encoding $\left< M \right>$ of $M$ to read the entry $\delta(\mathbf{q},a)$ of its transition table.

Update the configuration appropriately by overwriting the symbol $a$ at the tape head position, moving the tape head left or right, and updating the current state of the machine.

The machine $U$ continues simulating $M$ until the latter halts. At this point, $U$ erases the encoding $\left<M\right>$ of $M$ from the tape and the current state in the configuration string. This leaves the tape in the same state as $M$’s tape when it halts, and $U$ halts by accepting or rejecting to mimic the halting state of $M$.

The existence of a Universal Turing Machine is a remarkable result, and one that will return many times throughout this course.