Deterministic and nondeterministic Turing machines recognize the same languages

If a deterministic one-tape Turing machine recognizes $L$, then the same transition graph viewed as a nondeterministic machine with singleton choice sets also recognizes $L$.

Conversely, suppose a nondeterministic one-tape machine $N$ recognizes $L$. Build a deterministic multitape machine $D$ that, on input $w$, enumerates all finite branch-choice strings of lengths $0,1,2,\dots$. For each choice string $\alpha$ of length $d$, the machine $D$ simulates $N$ on $w$ for $d$ steps, following at the $r$th branching point the ${\alpha }_r$th available transition when that transition exists and abandoning $\alpha$ otherwise.

By [L1], $N$ accepts $w$ exactly when some finite accepting branch exists. If such a branch has length $d$, its sequence of local branch choices is one of the strings tested in step 1.2, so $D$ eventually finds it and accepts. If no accepting branch exists, every tested choice string fails to end in acceptance, so $D$ never accepts. Thus $D$ recognizes the same language as $N$.

Any temporary stay-put moves introduced while $D$ manages its work tapes can be removed by [L4], and then [L3] yields a deterministic one-tape machine recognizing the same language as $D$.

Steps 1.1 and 3.1 prove that nondeterministic and deterministic one-tape machines recognize exactly the same languages, in the sense of [L2].