TC

  • Turing Machines
    • Church-Turing Thesis
    • \mathbf{R},\mathbf{RE}, \mathbf{coRE}
    • Universal Turing Machine
  • Diagonalization

April 14, 2026

Given a context-free grammar G,

  • is \mathscr{L}(G)=\emptyset?
  • is \mathscr{L}(G) finite?

Given a context-free grammar G, and a word w,

  • is w\in \mathscr{L}(G)? Cocke-Kasami-Younger algorithm!

Theorem 1 (Leslie G. Valiant ’75) The CFG parsing problem can be solved in time \mathcal{O}(|G||w|^\omega), where \omega is the exponent of Boolean matrix multiplication1.

Theorem 2 (Lillian Lee ’02) Any CFG parser with time complexity \mathcal{O}(|G||w|^{3-\epsilon}) can be used to multiply m\times m Boolean matrices in time \mathcal{O}(m^{3-\epsilon/3}).

Given context-free grammars G_1, G_2,

  • is G_1 ambiguous?
  • is \mathscr{L}(G_1) a regular language?
  • is \mathscr{L}(G_1)=\{a,b\}^*?
  • is \mathscr{L}(G_1)=\mathscr{L}(G_2)?
  • is \mathscr{L}(G_1)\subseteq \mathscr{L}(G_2)?
  • is \mathscr{L}(G_1)\cap \mathscr{L}(G_2)=\emptyset?

There are no algorithms that always terminate and answer the questions above correctly!

We need a formalization of the intuitive notion of algorithm or effective procedure.

This is needed for negative results of the form:
“there is no algorithm that always terminates and solves problem X”.

For example, there is no algorithm that always terminates and

  • can determine whether a given a C++ program halts on a given input.
  • given a CFG G can determine whether G is ambiguous.
  • given a polynomial p(x_1,\dots,x_n) with integer coefficients can determine whether p has an integer solution.1
  • …many many more…

Turing Machines

Informally, a Turing machine is a DFA with an infinite tape and a read/write head that can move left and right.

  • Based on the current state of the DFA and the symbol read on the tape, the Turing machine can write a symbol on the tape, move the head one position left or right, and change its state.

Deterministic Turing Machine

M=({\color{red} Q},{\color{darkblue}\Sigma},{\color{brown}\Gamma},\delta,{\color{red}q_0,q_{accept},q_{reject}})

  • \color{red}{Q} finite set of states
    • \color{red} q_0 initial state
    • \color{red} q_{accept} accepting state
    • \color{red} q_{reject} rejecting state
  • \color{darkblue} \Sigma input alphabet
    • not containing \sqcup (the blank symbol) nor \triangleright (the left end marker)
  • \color{brown} \Gamma tape alphabet
    • containing \Sigma and \{\sqcup,\blacktriangleright\}
  • \delta: Q\setminus \{q_{accept},q_{reject}\} \times \Gamma\to Q\times \Gamma\times \{L,R\}

What is this TM doing?

\color{darkblue}\Sigma=\{0,1\}
\color{brown}\Gamma=\{0,1,\sqcup,\triangleright\}
\delta: Q\setminus \{q_{acc},q_{rej}\} \times \Gamma\to Q\times \Gamma\times \{\pm 1\}
\delta(q_0, 0) = (q_0, 0, R)
\delta(q_0, 1) = (q_0, 1, R)
\delta(q_0, \sqcup) = (q_1, \sqcup, R)
\delta(q_0, \triangleright) = (q_0, \triangleright, R)

What is this TM doing?

How can a DTM simulate a DFA?

What is this TM doing?

More examples of TMs in HW3 (next week) and here: https://turingmachinesimulator.com

  • M(x)\!\downarrow means that the Turing machine M halts on input x.

  • M(x)\!\uparrow means that the Turing machine M does not halt on input x (M on input x loops).

  • tape configuration (u, q, v), where

    • u is the left tape string,
    • q is the current state, and
    • v is the right tape string

\mathscr{L}(M) is the language recognized/accepted by the Turing machine M.

  • x\in \mathscr{L}(M) means that
    • M(x)\!\downarrow and
    • the final state reached is q_{accept}.
  • x\notin \mathscr{L}(M) means that
    • either M(x)\!\uparrow or
    • the final state reached is q_{reject}.

A partial function f:\Sigma^*\to \Sigma^* is computed by a Turing machine M if for every x\in \Sigma^* where f(x) is defined

  • M(x)\!\downarrow
  • the final state reached is q_{accept} and
  • the string left on the tape is f(x)

and for every x\in \Sigma^* where f(x) is not defined

  • either M(x)\!\uparrow or
  • the final state reached is q_{reject}.

Functions f : \mathbb N \to\mathbb N could be computed by a Turing machine: input and output are encoded in binary on the tape.

Theorem 3 The following computational models compute the same class of functions as Turing machines:

  • \lambda-calculus
  • \mu-recursive functions
  • Post machines
  • Register machines
  • Kleene recursivity
  • TMs with a tape infinite in both directions
  • TMs with multiple tapes
  • TMs with multiple heads
  • Nondeterministic TMs
  • TM on a queue
  • TMs with 2 or more stacks

Church-Turing Thesis The notion of Turing machine captures the intuitive notion of computability. That is, a function is computable if and only if it is computed by a Turing machine.

\mathbf{R}, \mathbf{RE}, \mathbf{coRE}

  • \mathbf{R} \ =\{L\subseteq \Sigma^* \mid \exists M ({\color{blue}M \text{ is a TM }} \text{ and }\ {\color{red}\forall x\in\Sigma^*, M(x)\!\downarrow} \text{ and } {\color{darkgreen}\mathscr{L}(M)=L})\}
    • recursive / decidable / computable languages
  • \mathbf{RE} \ =\{L\subseteq \Sigma^* \mid \exists M ({\color{blue}M \text{ is a TM }}\text{ and } {\color{darkgreen}\mathscr{L}(M)=L})\}
    • recursively enumerable / recognizable / semi-decidable / computably enumerable languages
  • \mathbf{coRE}\ =\{L \mid \overline L\in \mathbf{RE}\}.

Theorem 4 \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}

Proof.

  • (\subseteq) \mathbf{R}\subseteq \mathbf{RE} \mathbf{R}\subseteq \mathbf{coRE}, hence \mathbf{R}\subseteq \mathbf{RE}\cap \mathbf{coRE}
  • (\supseteq) in future classes

Theorem 5 There is a TM U s.t. for every TM M and every input x, U(\langle M,x\rangle)=M(x), where \langle M,x\rangle is an encoding of the pair (M,x) as a binary string.

The machine U is called a universal Turing machine and simulates the execution of M on x.

  1. Check the input word \langle M, x \rangle, for correctness, i.e., check whether \langle M \rangle describes a valid Turing Machine, and whether x is a string over the input alphabet of M.
  2. Write the starting configuration (\lambda, q0, x) of M onto the work tape.
  3. If the current configuration for M is a halting configuration, go to step 7.
  4. Find an argument pair matching the current state and input character of M in the encoding of M ’s transition function.
  5. Update the current state and left and right tape string according to the value triple found in M’s transition function.
  6. Repeat from step 3.
  7. If M ’s current state is the accept state, accept; if the current state is the reject state, reject.

Countable and Uncountable Sets

A set is countable if it is finite or if there exists a bijection between it and \mathbb{N}.

  • Is \mathbb{Z} countable?
  • Is \{0,1\}^* countable?
  • Is \mathbb{Q} countable?

Otherwise a set is uncountable.

Theorem 6 If A\subseteq B and B is countable, then A is countable.

Exercise 1 The set of all Turing machines is countable.

Two sets have the same size (or cardinality) if there exists a bijection between them.

Theorem 7 \mathbb{R}, \mathbb{R}\cap (0,1), \mathscr{P}(\mathbb{N}), and \mathscr{P}(\{0,1\}^*) all have the same cardinality.1

Continuum Hypothesis
There is no set whose cardinality is strictly between \aleph_0 (the cardinality of \mathbb{N}) and \mathfrak{c} (the cardinality of \mathbb{R}).2



Diagonalization

Theorem 8 \mathscr{P}(\{0,1\}^*) is not countable.

Proof.

  • Fix an ordering on the words in \{0,1\}^* (e.g., by length and then lexicographically).
  • By contradiction assume \mathscr{P}(\{0,1\}^*) is countable.
    • That is there exists f:\mathbb{N}\to \mathscr{P}(\{0,1\}^*) which is a bijection.
  • w n-th word in \{0,1\}^* is in f(n) or not.
  • D=\{w\in \{0,1\}^* \mid w\not\in f(n) \text{ where $n$ is the index of $w$}\}.
  • Is D in the image of f?
  • Contradiction.

Corollary 1 \mathbb{R} and \mathscr{P}(\mathbb{N}) are not countable.

Exercise 2 There are uncountably many languages (say over \{0,1\}) not recognized by any Turing machine.

Any explicit example of such a language? Yes! tomorrow’s class.