11 Nondeterminism, Equivalence, and Countability

Lecture from: 21.10.2025 | Video: Videos ETHZ

Nondeterministic Turing Machines (NTMs)

We’ve introduced the deterministic Turing Machine (DTM) as our standard model of computation. Now, we explore a variant that seems much more powerful: the Nondeterministic Turing Machine (NTM).

Intuition: Guessing, Not Randomness

A common misconception is that “nondeterminism” means “randomness.” This is not the case. We are not flipping coins or dealing with probabilities.

• Randomness: A machine makes a random choice, and we care about the probability of reaching a correct answer.
• Nondeterminism: A machine can choose from multiple valid next steps. It “guesses” the correct path. If any sequence of choices leads to acceptance, the machine accepts.

Think of it as having a magical ability to always pick the right path in a maze, or exploring all paths in parallel universes.

Formal Definition of an NTM

An NTM is defined almost exactly like a DTM, as a 7-tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{acc},q_{rej})$. The only difference lies in the transition function $\delta$.

In a DTM, the transition function maps a state and a symbol to one specific next move:

$$\delta :(Q\setminus \{q_{acc},q_{rej}\})\times \Gamma \to Q\times \Gamma \times \{L,R,N\}$$

In an NTM, the transition function maps to a set of possible next moves (the power set):

$$\delta :(Q\setminus \{q_{acc},q_{rej}\})\times \Gamma \to \mathcal{P}(Q\times \Gamma \times \{L,R,N\})$$

This means that for a given state and tape symbol, the machine might have zero, one, or multiple valid transitions.

Computation Trees and Acceptance

Since an NTM can branch at each step, its computation on a specific input $w$ is not a single line, but a computation tree.

• The root is the start configuration q_0 \ w$.
• Each node is a configuration.
• The children of a node are all the configurations reachable in one step according to $\delta$.

Acceptance Condition: An NTM accepts an input $w$ if there exists at least one path from the root to a configuration containing the accept state $q_{acc}$.

• If multiple paths accept, great.
• If some paths loop forever or reject, but one accepts, the machine still accepts.
• The machine rejects only if all possible computation paths halt and reject.

Example: The Traveling Salesperson Problem (TSP)

Consider the problem of deciding if a graph $G$ has a Hamiltonian Cycle (a cycle visiting every node exactly once).

• Deterministic Approach: A DTM would have to systematically generate and check every possible permutation of nodes. This corresponds to a brute-force search, taking roughly $O(n!)$ time.
• Nondeterministic Approach: An NTM can solve this “efficiently” (in polynomial time):
  1. Guess: Nondeterministically write a list of $n$ vertices on the tape. This corresponds to “guessing” a permutation. Since the machine can branch, one of its computation paths will write the correct Hamiltonian cycle (if one exists).
  2. Verify: Deterministically check if the list on the tape is a valid cycle in $G$. This takes polynomial time.

If the graph has a cycle, there is a path in the computation tree where the machine guesses it correctly and accepts. Thus, the NTM accepts the language of Hamiltonian graphs efficiently. This capability is the core of the complexity class NP (Nondeterministic Polynomial time).

Equivalence of DTMs and NTMs

Does this magical guessing ability allow NTMs to solve problems that DTMs simply cannot (regardless of time)? The answer is no.

Theorem: Every Nondeterministic Turing Machine has an equivalent Deterministic Turing Machine.

$$L(NTM)=L(DTM)$$

Proof Idea: Breadth-First Search

We can simulate an NTM $N$ using a DTM $D$. The DTM will explore the computation tree of $N$.

• Why not Depth-First Search (DFS)? The computation tree of $N$ might have infinite paths (loops). If $D$ uses DFS, it might go down an infinite non-accepting path and never find the accepting state on a different branch.
• Solution: Breadth-First Search (BFS). $D$ explores the tree layer by layer.
  1. Check the start configuration (depth 0).
  2. Check all configurations reachable in 1 step (depth 1).
  3. Check all configurations reachable in 2 steps (depth 2).
  4. … and so on.

Since the branching factor of $N$ is finite (limited by $|\delta |$), each level of the tree is finite. If an accepting configuration exists, it must appear at some finite depth $d$. A BFS is guaranteed to find it eventually.

Construction of $D$: $D$ can be a 3-tape machine:

1. Input tape: Holds the original input $w$.
2. Simulation tape: Used to simulate one specific path of $N$.
3. Address tape: Keeps track of which node in the tree we are currently visiting (e.g., using a string of numbers to represent “choice 1, then choice 3, then choice 2…”).

$D$ systematically generates all addresses (sequences of choices) in lexicographical order (short first). For each address, it copies $w$ to the simulation tape and runs $N$ following those specific choices. If $N$ accepts, $D$ accepts.

Implication: NTMs and DTMs accept the same class of languages (${\mathcal{L}}_{RE}$). Nondeterminism affects efficiency (time complexity), but not decidability.

Enumerating Turing Machines

We now turn to a concept crucial for proving undecidability: Countability.

Encoding Turing Machines

A Turing Machine is a finite object. It’s defined by a 7-tuple with finite sets of states and symbols and a finite transition table. This means we can encode any TM as a string (e.g., a binary string).

• Assign numbers to states $q_0,q_1,\dots$.
• Assign numbers to tape symbols $X_1,X_2,\dots$.
• Encode the transition function as a list of rules like (state, read) -> (new_state, write, move).

Just as we can compile a Python program into a binary executable, we can serialize a TM $M$ into a string $⟨M⟩\in \{0,1{\}}^{\ast }$.

The Set of TMs is Countable

Since every TM can be encoded as a binary string, the set of all Turing Machines is a subset of the set of all binary strings $\{0,1{\}}^{\ast }$. We know $\{0,1{\}}^{\ast }$ is countable (we can list them: $\lambda ,0,1,00,01,\dots$). Therefore, the set of all Turing Machines is also countable. We can create a canonical list of all TMs: $M_1,M_2,M_3,\dots$.

Countability and Diagonalization

To understand the limits of computation, we need to compare the size of the set of algorithms (TMs) vs. the set of problems (languages).

Countable Sets

A set $A$ is countable if there exists a surjective function $f:\mathbb{N}\to A$. Equivalently, we can list the elements of $A$ as $a_1,a_2,a_3,\dots$.

• Finite sets are countable.
• $\mathbb{N}$ (natural numbers) is countable.
• $\mathbb{Z}$ (integers) is countable (list: $0,1,-1,2,-2,\dots$).
• ${\Sigma }^{\ast }$ (all strings) is countable.

The Pairs of Natural Numbers ($\mathbb{N}\times \mathbb{N}$)

Is the set of pairs $(i,j)$ countable? It seems “larger” than $\mathbb{N}$, like a 2D plane vs. a line. However, Cantor showed it is countable using a diagonalization argument (specifically, traversing anti-diagonals).

We can list pairs by the sum of their indices $k=i+j$:

• Sum 0: $(0,0)$
• Sum 1: $(0,1),(1,0)$
• Sum 2: $(0,2),(1,1),(2,0)$
• …

This gives us a valid enumeration (bijection with $\mathbb{N}$):

$$(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),\dots$$

This technique proves that any finite Cartesian product of countable sets is countable (e.g., ${\mathbb{N}}^k$, $\mathbb{Q}$).

Conclusion: Since the set of all possible TMs is countable, but (as we will see next time) the set of all possible languages is uncountable, there are infinitely many languages that cannot be recognized by any Turing Machine. Most problems are unsolvable!