Question bank — Variants — multi-tape TM, non-deterministic TM, all equivalent

False. Every $k$-tape TM is simulated step-for-step by a single-tape TM (blocks separated by #, dotted heads), so they recognize exactly the same languages — only the single-tape version is slower.

False. The breadth-first branch search simulates any NTM on a DTM; acceptance ("some branch accepts") is faithfully reproduced, so the language class is identical — see Non-determinism in Finite Automata (NFA = DFA) for the same phenomenon one level down.

False. It runs in $O(t(n{)}^2)$: each simulated step needs about two sweeps across the $O(t(n))$-long used region, giving a quadratic (not identical) slowdown.

False (as far as anyone knows). The known simulation is $2^{O(t(n))}$ because the computation tree has up to $b^{t(n)}$ nodes; whether a polynomial simulation exists is exactly the open P vs NP problem.

False. Exponential cost is about speed, not power. The DTM eventually accepts exactly the same strings, so they are equal in power — the blow-up is a complexity fact, not a computability one.

False. Non-determinism is a mathematical convenience for defining acceptance ("some branch accepts"), not a physical oracle. A DTM realises it mechanically by searching all branches — no magic, just slower.

True. If a small tweak had added power, "computable" would be fragile and arbitrary; the fact that every reasonable tweak collapses to one model is the strongest empirical support that we captured the right notion of algorithm.

False. You fold the negative half onto the positive half using a two-track encoding; the standard model simulates it, so same power (again just bookkeeping).

False. Extra heads are just more "dotted positions" to track in the finite control, exactly like extra tapes — simulated by one head, same power.

Error: DFS can dive into an infinite non-accepting branch and never return, missing a nearby accepting branch. We must use breadth-first search so every finite-depth accepting branch is reached.

Error: The address tape stores which choice (a digit in $\{1,\dots ,b\}$) to take at each step, where $b$ is the maximum number of options in any $\delta$ entry — not the states. States are computed by simulating, not stored as the address.

Error: You need (at least) two sweeps: the first reads all $k$ dotted symbols so the control can compute $\delta$; the second writes the new symbols and moves each dot. One sweep can't read-all-then-write-all.

Error: Overwriting # would destroy the block boundary. Instead you shift everything to the right to insert a fresh blank, growing that virtual tape while keeping all delimiters intact.

Error: It accepts if at least one branch accepts. Requiring all branches would be a different (universal / co-nondeterministic) acceptance rule.

Not an error — this is correct. Because 3-tape ≡ 1-tape is already established, using three tapes (input, working copy, address) is just a convenience that adds no power; it can itself be flattened to one tape afterward.

Error: $\delta$ is a finite table; it maps a finite tuple of read symbols to a fixed output. Finiteness of the control is exactly what lets a single-tape machine record the read symbols and reproduce the step.

Because power/computability asks which problems are solvable in principle; a slow-but-correct machine still solves the problem. Timing lives in a separate axis, Time Complexity and Big-O, precisely so we can say "same power, different speed."

The simulation is correct but costs $2^{O(t(n))}$; P vs NP asks whether every NTM that accepts in polynomial time can be simulated in polynomial time deterministically. If yes, P = NP; nobody knows, so the exponent stays.

In $t(n)$ steps no head moves past $t(n)$ cells, so the used region is $O(t(n))$ long. Each simulated step sweeps that whole region ($O(t(n))$ work), and there are $t(n)$ steps, giving $t(n)\cdot O(t(n))=O(t(n{)}^2)$.

A dotted symbol $\dot{x}$ carries both pieces of information at once — the tape content $x$ and "a head is here" — without consuming an extra cell or breaking the block layout, so the finite control can read position and content together.

Every branch must start from the same original input; if a branch modified tape 1, the next branch would begin from corrupted data. Keeping it read-only lets us copy a fresh clone to the working tape each time.

Because all reasonable variants compute the same class, there is a single model-independent notion of "computable," so one machine that can simulate any TM captures all of computation, not just one flavour.

The definition lets us "declare success if any branch works," skipping the search in the model. But a real deterministic device must actually do the search, so the apparent speed-up is only realised if a clever deterministic algorithm exists — again the P vs NP problem.

That branch simply halts without accepting; BFS moves on to the next address. Zero-option nodes are non-accepting leaves and never block other branches from being explored.

The branch is invalid, so the DTM aborts it and increments to the next address. Skipping invalid addresses costs nothing in correctness because they correspond to no real branch.

It merely recognizes: the DTM keeps exploring ever-deeper addresses forever, never accepting and never halting, mirroring that no finite accepting branch exists — see Decidability and Recognizability.

Yes, take $k=1$; the multi-tape definition with one tape is the ordinary TM, so the equivalence theorem trivially holds in that degenerate direction.

$b=1$: every $\delta$ entry has exactly one option, the tree is a single line, and the "search" has one address of each length — the exponential $b^{t(n)}=1^{t(n)}=1$ collapses, confirming a DTM simulating a DTM has no blow-up.

The simulation still lays out $k$ blocks separated by #; the unused blocks just hold blanks with a dotted blank for their idle head. Correctness is unaffected — the extra empty blocks cost only linear space.

Yes. A stay move is simulated by moving right then left (or by encoding it in the control), adding no power — one more harmless bookkeeping variant that collapses to the base model.