Decidability and Undecidability

“I was peeling a red apple from the garden when I suddenly understood that life would only ever give me a series of wonderfully insoluble problems. With that thought, an ocean of profound peace entered my heart.”
—Christian Bobin

Given an input string, a Turing Machine can accept, reject, or run forever without providing an answer. This third possibililty means we have to be more careful about our definitions.

The Language of a Turing Machine

Definition

A Turing Machine $M$ accepts a string $w$ if $M$ halts-and-accepts when started on a tape containing the string $w$ .

A Turing Machine $M$ rejects a string $w$ if $M$ halts-and-rejects when started on a tape containing the string $w$ .

The language of a Turing Machine $M$ , denoted $L(M)$ , is the set of strings that $M$ accepts.

So if a string $w$ is not in $L(M)$ , there are be two potential reasons: either $M$ eventually rejects $w$ , or $M$ runs forever without specifically accepting or rejecting $w$ .

Decidability and Undecidability

Definition

A language is decidable if it is the language of some terminating TM.

So the following are all equivalent ways of saying that a language $L$ is decidable:

$L$ is the language of some TM $M$ that always terminates.
There exists a TM $M$ such that $M$ accepts $w$ iff $w\in L$ and $M$ rejects $w$ iff $w\not\in L$ .
There exists a TM $M$ such that $M$ accepts every string in $L$ , and rejects any string not in $L$ .
There exists a TM $M$ that always (eventually) tells us whether or not its input is in $L$ .

Definition

A language is undecidable if it is not decidable.

The family of all decidable languages is closed under union, intersection, and complement. We prove the last of these:

Theorem

If $L$ is a decidable language, then $L^c$ is decidable.

Proof:
Assume $L$ is a decidable language.

Then there is a TM $M$ which decides $L$ (i.e., accepts every string in $L$ and rejects every string not in $L$ ).

Let $M'$ be a copy of $M$ except we swap transitions to the accept and reject states.

Then $M'$ accepts every string not in $L$ (i.e., every string in $L^c$ ) and rejects every string in $L$ (i.e., every string not in $L^c$ ).

Thus $M'$ decides $L^c$ , and $L^c$ is decidable.

Decidability and Undecidability of Acceptance

We now turn to our first concrete examples of an undecidable language, $A_\mathrm{TM}$ . We start with some simpler (decidable) languages for contrast.

Definition

The notation $\langle \cdots \rangle$ means ” $\cdots$ encoded as a string.”

For example, if $M$ is a Turing Machine then $\langle M\rangle$ is the full specification of $M$ as a finite string.

Similarly if $D$ is a DFA and $w$ is a string in the alphabet of that DFA, then $\langle D,w\rangle$ is a string that specifies both a description of $D$ (its states, transitions, etc.) and a the contents of the string $w$ .

Example

The following languages are decidable:

$A_\mathrm{DFA} = \{\ \langle D, w\rangle\ \ |\ D \mathrm{~a~DFA},\ w\in L(D)\ \}$
$A_\mathrm{NFA} = \{\ \langle N, w\rangle\ \ |\ N \mathrm{an~NFA},\ w\in L(N)\ \}$
$A_\mathrm{RE} = \{\ \langle R, w\rangle\ \ |\ R \mathrm{~a~regexp},\ w\in L(R)\ \ \}$
$A_\mathrm{CFG} = \{\ \langle G, w\rangle\ \ |\ G \mathrm{~a~CFG},\ w\in L(G)\ \}$

Proof:

Given $D$ and $w$ , follow the appropriate transitions corresponding to $w$ in the automaton $D$ , and check whether the final state is accepting.
Use the subset construction to turn $N$ into an equivalent DFA, and check whether $w$ is accepted by that DFA. (Or, run $w$ through the NFA, and keep track at each step what possible states $N$ could be in.)
Convert $R$ into an NFA, and then check whether $w$ is accepted by that NFA.
Use a parsing algorithm like the CYK Algorithm to determine whether $w$ can be produced by grammar $G$ .

However, when we move from DFAs and CFGs to Turing Machines, it is undecidable whether a machine will accept a given string.

Example

The language

A_\mathrm{TM} = \{\ \langle M, w\rangle\ |\ M \mathrm{~a~TM},\ w\in L(M)\ \}

is undecidable.

Proof (by contradiction):

Suppose $A_\mathrm{TM}$ were decidable.

Then there is a Turing Machine (a piece of code) decide_Atm that took as input $\langle M,w\rangle$ (a string containing both the specification/code for a machine $M$ and a specific input string $w$ for the machine $M$ ) and always told us whether $M$ would accept $w$ or not.

Note: decide_Atm can’t check this by running $M$ on $w$ , because that might never terminate. decide_Atm would presumably study the definition/code of $M$ and the input string $w$ and do some arbitrarily complex calculations to predict the behavior of $M$ on that input.

We could then construct a “bigger” Turing Machine C to perform a calculation according to the following pseudocode:

def Cantor(x):
      return not (decide_Atm(x, x))

The idea is that we would run Cantor on the description $\langle M\rangle$ of some a Turing Machine; Cantor would use the procedure decide_Atm to ask whether Turing Machine $M$ would accept the string $\langle M\rangle$ or not (i.e., whether $M$ ’s source code is a string that machine $M$ would accept). Whatever that answer is, C then returns the opposite.

Since we have assumed decide_Atm can be implemented and always returns an answer, we can also implement C and be sure it always returns an answer as well.

For example, if $M$ was a Turing Machine that checked whether its input was an even-length palindrome, then $\mathtt{Cantor}(\langle M\rangle)$ would probably return True (accept):

The code of a TM for checking palindromes is probably not a palindrome.
So, $M$ would probably not accept its own source code $\langle M\rangle$ .
decide_Atm( $\langle M\rangle, \langle M\rangle$ ) would predict that and return False (reject).
Cantor negates this, and returns True (accepts).

So far, so good. The problem is this: we’ve implemented Cantor as a piece of code (a Turing Machine). What happens if instead of applying Cantor to the code for a palindrome-checker, we apply Cantor to its own source code? According to the definition

def Cantor(x):
      return not (decide_Atm(x, x))

the call Cantor( $\langle\mathtt{Cantor}\rangle$ ) would ask decide_ATM whether the machine Cantor accepts when given its own source code as input, and then returns the opposite answer. This is a problem, because

Cantor can’t accept its own source code. If it did, decide_Atm would predict this fact. Then Cantor would negate this answer and return False (rejecting its own source code).
Cantor can’t reject its own source code. If it did, decide_Atm would predict that fact. Then Cantor would negate this answer and return True (accepting its own source code).
Cantor can’t compute forever; it just calls decide_Atm (which always returns an answer), and takes one more step to negate that answer.

We have reached a contradition: Cantor( $\langle\mathtt{Cantor}\rangle$ ) cannot accept, cannot reject, and cannot run forever.

Therefore, our assumption (that we could implement a decider for $A_\mathrm{TM}$ ) must be wrong, and $A_\mathrm{TM}$ is not decidable.

One might worry that there’s something fishy about applying a program to its own source code, but this happens all the time in the real world, e.g.,

The Unix utility wc can be used to count the number of lines in a text file. This program is implemented in C; if we wanted to whether this code is long and complicated, it would be perfectly reasonably to run wc on its own code w.c to see how many lines are in the source code.
The Visual Studio Code editor is written as a collection of JavaScript and TypeScript files. If we wanted to add a new feature to VSCode, we could edit the JavaScript and TypeScript files using VSCode to add the functionality. When we restart the editor, the new feature will be available.
The clang++ C++ compiler is written in C++. To add a new feature to the compiler (e.g., when a new standard for C++ adds extra features to the C++ languages), we edit the C++ source, compile that C++ source with the old clang++ compiler, and produce a new clang++ executable having the new feature.

So the idea of applying a program to its own source code is not inherently contradictory.

What Does This Mean?

Saying that $A_\mathrm{TM}$ is undecidable means that there is no Turing Machine (and hence no code and no algorithm) that can take an arbitrary TM and an arbitrary input, and correctly predict (in finite time) whether this TM will accept that input.

It does not mean we can never answer the question! It’s quite easy to build a TM that never accepts. If we ask whether this particular machine accepts $\epsilon$ , we have no problem deciding the answer is “no.”

Conversely, we might be able to look at a more interesting Turing Machine and realize it accepts all (and only) even-length palindromes.

But there is no algorithm for deciding acceptance that works in all cases.