180 Complexity — Diagonalization

180.1 Overview

This module proves uncomputability by diagonalization [AB09, §1.5, Theorem 1.10]: it defines the diagonal function \(\mathrm{UC}\) of a representation scheme for Turing machines and shows that \(\mathrm{UC}\) is not computable, for every such scheme — effective or not. The result uses only machines-as-strings, not the universal machine.

180.2 Declarations

Definition 180.1 Diagonal function of a representation scheme

✓

Fix a representation scheme \(c\) for Turing machines in code normal form (one work tape, binary alphabet): a total decoding assigning to every bit string a machine, together with an encoding that the decoding inverts. The diagonal function \(\mathrm{UC}_c : \{ 0,1\} ^* \to \{ 0,1\} \) maps a bit string \(\alpha \) to \(\mathrm{false}\) if the machine that \(\alpha \) denotes under \(c\), run on the input \(\alpha \) itself, halts after some finite number of steps with completed output the one-bit string \([\mathrm{true}]\) — that is, if the machine accepts its own representation. In every other case — the machine diverges on \(\alpha \), or halts with any completed output other than \([\mathrm{true}]\) — the value is \(\mathrm{true}\). ([AB09, §1.5] writes: \(UC(\alpha ) = 0\) if \(M_\alpha (\alpha ) = 1\), and \(UC(\alpha ) = 1\) otherwise.)

Theorem 180.2 Characterization of the value false of the diagonal function

✓

Let \(c\) be a representation scheme for Turing machines in code normal form (one work tape, binary alphabet; a total decoding of bit strings to machines, inverted by the encoding), and let \(\alpha \) be a bit string. Then the diagonal function of \(c\) takes the value \(\mathrm{false}\) at \(\alpha \) — i.e. \(\mathrm{UC}_c(\alpha ) = \mathrm{false}\) — if and only if there exists a number of steps \(t\) within which the machine denoted by \(\alpha \) under \(c\), run on the input \(\alpha \) itself, halts with completed output the one-bit string \([\mathrm{true}]\).

Theorem 180.3 Characterization of the value true of the diagonal function

✓

Let \(c\) be a representation scheme for Turing machines in code normal form (one work tape, binary alphabet; a total decoding of bit strings to machines, inverted by the encoding), and let \(\alpha \) be a bit string. Then the diagonal function of \(c\) takes the value \(\mathrm{true}\) at \(\alpha \) — i.e. \(\mathrm{UC}_c(\alpha ) = \mathrm{true}\) — if and only if there is no number of steps \(t\) within which the machine denoted by \(\alpha \) under \(c\), run on the input \(\alpha \) itself, halts with completed output the one-bit string \([\mathrm{true}]\): the machine diverges on \(\alpha \), or halts with a completed output other than \([\mathrm{true}]\).

Theorem 180.4 Uncomputability of the diagonal function

✓

Let \(c\) be any representation scheme for Turing machines in code normal form (one work tape, binary alphabet; a total decoding of bit strings to machines, inverted by the encoding), effective or not, and let \(\mathrm{UC}_c\) be its diagonal function: \(\mathrm{UC}_c(\alpha ) = \mathrm{false}\) if the machine denoted by \(\alpha \) under \(c\) halts on the input \(\alpha \) itself with completed output the one-bit string \([\mathrm{true}]\), and \(\mathrm{UC}_c(\alpha ) = \mathrm{true}\) otherwise. Then the total function on bit strings \(\alpha \mapsto [\mathrm{UC}_c(\alpha )]\), returning the one-bit string whose single bit is the value of the diagonal function, is not computable: no finite Turing machine over the binary alphabet halts on every input \(\alpha \) with \([\mathrm{UC}_c(\alpha )]\) on its output tape [AB09, Theorem 1.10].