Foundations — Variants — multi-tape TM, non-deterministic TM, all equivalent

Before you can appreciate why multi-tape and non-deterministic machines are no more powerful than the basic one, you need every symbol they are built from. This page assumes nothing. We build each piece, draw it, then say why the topic needs it. Read top to bottom — each item uses only things defined above it.

0. The tape and the head — the physical picture

Everything starts with one image: an infinitely long strip of paper divided into square cells, and a little read/write head parked over one cell.

Why the topic needs this. Every "variant" in the parent note is just a change to this picture: more strips (multi-tape) or more choices about where the head goes (non-deterministic). If you can see one head on one tape, you can see all the variants as edits to that drawing.

1. Symbols and alphabets — $\Sigma$ and $\Gamma$

The head reads and writes symbols. We need names for the two pools of symbols allowed.

The picture: $\Sigma$ is the small box of letters you're allowed to start with; $\Gamma$ is the bigger box of letters you're allowed to scribble with. Always $\Sigma \subseteq \Gamma$ (Sigma sits inside Gamma).

2. Strings, $w$, and length $n$

The picture: $w$ is what's already printed on the first cells of tape 1 when the machine wakes up; everything to its right is $\bigsqcup$. The number $n$ measures "how big is this problem," and every timing claim in the parent note (like $O(t(n{)}^2)$) is measured as a function of $n$.

3. States and the control — $Q$, $q_0$, accept/reject

The head needs a "mood" or "mental state" telling it what to do next. That's the finite control.

The symbol $\in$ (read "is an element of") just says $q_0$ is one of the moods listed in $Q$.

4. Sets of options — $\mathcal{P}(\cdot )$, ${\Gamma }^k$, and $\{L,R\}$

The non-deterministic definition uses $\mathcal{P}(\cdots )$ and the multi-tape one uses ${\Gamma }^k$. Let's earn both.

The picture: if $S$ is a menu, $\mathcal{P}(S)$ is the list of all possible combos you could order, including "order nothing" and "order everything."

Why the topic needs it. A non-deterministic machine, at one step, may have several allowed moves. "A set of allowed moves" is exactly "an element of $\mathcal{P}(\text{all moves})$" — so the right-hand side of the NTM transition landing in $\mathcal{P}(\cdots )$ is precisely "returns a set of choices."

The picture for ${\Gamma }^k$: instead of one head reading one symbol, imagine $k$ heads on $k$ strips; a single "reading" is now the whole row of symbols under all heads at once — that's the tuple.

5. Functions and the arrow $\to$ — the transition rule $\delta$

Everything above assembles into $\delta$, the rulebook.

Now read the parent's two transition functions with fresh eyes:

The single visual difference: deterministic returns one arrow out of each situation; non-deterministic returns a fan of arrows.

6. Determinism vs non-determinism — line vs tree

Look at the figure: on the left, one arrow leads to the next box forever — a path. On the right, boxes split into children — a tree. The parent's whole NTM→DTM simulation is just: a line-machine walks the tree of a fan-machine, one branch at a time.

7. Reading the cost symbols — $t(n)$, $O(\cdot )$, $2^{O(\cdot )}$

The parent states timing results. Here's what those symbols say.

See Time Complexity and Big-O for the full grammar of these symbols. The picture to keep: $O(t^2)$ (multi-tape slowdown) is a gentle parabola; $2^{O(t)}$ (NTM blow-up) is a wall that shoots to the sky. Same power, wildly different speed — the seed of the P vs NP problem.

Prerequisite map

Each foundation feeds the next; together they let you read every symbol in the parent theorem and follow both simulations.

Equipment checklist

Test yourself — cover the right side and answer before revealing.

Ready? Return to the parent topic and the equivalence proofs will read as sentences, not symbols. Related building blocks: Turing Machine — formal definition, Church–Turing Thesis, Non-determinism in Finite Automata (NFA = DFA).