skip to content

Why must a deterministic simulation of a nondeterministic tape machine explore its configuration tree breadth-first?

level: seniorimportance: nice to knowfreq 26%

answer

  1. the table returns a set
  2. acceptance needs one branch only
  3. the run is a tree, not a line
  4. an endless branch traps a depth-first walk
  5. levels, not paths: b to the d

basics

~20 s

Because one branch may run forever. A depth-first walk can descend into it and never return to the short accepting branch beside it, while a level-by-level sweep reaches every configuration at a given depth in finite time.

solid answer

~40 s

In a nondeterministic tape machine the table maps a state-symbol pair to a *set* of allowed successors, so a run is not a line of configurations but a tree that branches wherever several entries apply. The machine accepts when at least one branch reaches an accepting halting configuration — the others may reject or never stop. A deterministic simulator has to search that tree. Depth-first is unsafe: an endless branch traps the walk, and the accepting branch two levels down is never reached. Breadth-first (or repeated depth-limited search) visits every configuration at depth d before any at depth d+1, so an accepting configuration at depth d is always found. The price is the frontier: with branching factor b there are on the order of b to the power d configurations to examine.

code

pseudocode · 12 lines
pseudocode
frontier = queue containing only the start configuration

while frontier is not empty:
    c = remove_front(frontier)                  # oldest first, so level by level
    if c is halting and accepting:
        report accept and stop
    if c is halting:
        continue                                # this branch is finished, others are not
    for each successor s allowed by the table for c:
        add_back(frontier, s)

# note: no branch is ever abandoned, and nothing here ever reports reject

go deeper

for a junior

Know the shape: a nondeterministic machine's table may allow several next steps for the same situation, and the input counts as accepted if any one chain of choices ends in acceptance.

for a middle

Explain the configuration tree and why acceptance is existential, and be able to say why a level-by-level search finds an accepting branch that a plunge down one path can miss entirely.

for a senior

Carry the cost honestly: about b to the d configurations for branching factor b and depth d, plus the memory of the frontier or the replay cost of rebuilding a branch's tape, and separate that from any claim about what is computable.

for a principal

Resist the argument that a design gets something for free because a model is allowed to guess. Guessing defines an outcome; a real system still has to pay for the search, and the frontier is where that bill arrives.

## What nondeterminism changes in the table A deterministic machine's table gives at most one entry per (state, scanned symbol) pair. A nondeterministic one gives a **set** of allowed entries for a pair: the same state and symbol may license writing `1` and moving right, or writing the blank and moving left. Nothing chooses between them; the model simply declares both to be legal continuations. Acceptance is therefore defined **existentially**: the machine accepts an input when *at least one* sequence of legal choices reaches an accepting halting configuration. Branches that reject, and branches that never halt at all, do not spoil that. This is a definition, not a machine that runs — there is no hardware in the model that follows several choices, and no resource account in which the branching is free. ## The configuration tree Unrolling the choices gives a tree: - the **root** is the start configuration — start state, input on the tape, head at the left end; - a node's **children** are the configurations reachable by one legal entry for that node's state and scanned symbol; - the **branching factor** `b` is the largest number of entries the table offers for any pair; - a **path** from the root is one possible run, and the input is accepted when some path hits an accepting halting configuration. Two features of this tree drive everything else. It is finitely branching, since the table is a finite object. But it need not be finite in depth: a branch can descend forever, exactly as a deterministic run can fail to halt. ## Why the traversal order is the whole question | traversal | behaviour on a tree with one endless branch | finds an accepting node at depth d? | |---|---|---| | depth-first | descends the endless branch and never returns | not reliably — it may never reach that level | | breadth-first | expands level by level, so the endless branch contributes one node per level | yes, after examining the levels above it | | repeated depth-limited search | re-runs depth-first with an increasing cut-off, so no run is trapped | yes, at the cost of revisiting shallow nodes | Depth-first fails for a reason worth stating precisely: it is not that it is slower, but that it may never terminate on a branch that has no answer in it, while the answer sits on a sibling branch it never returns to. Breadth-first cannot be trapped, because it never commits to following a path further than one step before considering every alternative at the same depth. ## What the search costs With branching factor `b`, the number of configurations at depth at most `d` is on the order of `b` to the power `d`. Finding an accepting configuration at depth d therefore means examining exponentially many configurations in d. There is a further factor on top of that: a simulator that keeps only the choice sequence has to replay a branch from the start to rebuild its tape, and one that stores configurations pays memory proportional to the frontier, which is the widest level of the tree. So the conclusion has two halves, and the second is the one candidates drop: 1. **Power is unchanged.** Every input the nondeterministic machine accepts, the deterministic simulator accepts, because the search is exhaustive on every finite depth. 2. **Speed is not.** The construction turns one nondeterministic step into exponentially many deterministic ones, and that cost is inherent to *this construction*, which is a statement about the simulation and not a claim that no better method could exist for a particular problem. ## How to talk about it without overclaiming - Guessing in this model is a way of *defining* acceptance, not a way of getting work done for free. - 'All the branches run in parallel' is a harmless picture only until someone uses it to argue that the branching costs nothing; the frontier is the resource the picture hides. - Rejection is the awkward direction: a search that has not found an accepting configuration has not shown there is none, since deeper levels remain, which is why simulators of this shape announce acceptance and otherwise keep going.

  • Why does repeated depth-limited search work when plain depth-first does not?
    Because every individual search is cut off at a fixed depth, so no run can be trapped by an endless branch. Raising the cut-off by one each round means an accepting configuration at depth d is found on round d. The cost is revisiting the shallow levels repeatedly, which is dominated by the widest level explored.
  • What does the simulator do when it has not found an accepting configuration?
    It keeps going. Not having found one says nothing, because unexplored depth always remains, so this construction reports acceptance and otherwise continues indefinitely. Turning it into something that also answers in the other direction requires a bound on how deep the search must go, which the model alone does not supply.
  • Is the branching factor the same as the number of states?
    No. The branching factor is the largest number of entries the table offers for a single state-and-symbol pair — often two or three — while the state count is the size of the finite control. A machine with many states can be entirely deterministic, with a branching factor of one and no tree at all.

saying these in an interview costs you the question

  • Says a guessing machine computes things no deterministic machine can
  • Claims the simulator can simply pick the branch that accepts
  • Believes depth-first search over the configuration tree is equally safe
  • Says the branches all run at once, so guessing costs nothing
  • Claims the search cost is polynomial in the depth of the tree