The configuration graph of a machine on an input

Let $N$ be either a deterministic one-tape Turing machine or a nondeterministic one-tape Turing machine, and fix an input word $w$.

Write $C{⇝}_N{C}^{\mathrm{\prime }}$ when $C^{\mathrm{\prime }}$ follows $C$ by one legal step of $N$: in the deterministic case this means $C{⊢}_N{C}^{\mathrm{\prime }}$ in the sense of The one-step configuration relation, and in the nondeterministic case it means that one allowed instruction of $N$ changes $C$ to $C^{\mathrm{\prime }}$ by the same local rewrite and head-move rule.

The configuration graph of $N$ on $w$ is the directed graph $G_N(w)=(V,A)$ whose vertex set $V$ is the set of all configurations reachable from the initial configuration $(q_0,0,t_w)$ by finitely many legal steps, where $t_w$ is the input tape for $w$, and whose arc set $A\subseteq V\times V$ consists of the ordered pairs $(C,C^{\mathrm{\prime }})$ such that $C{⇝}_N{C}^{\mathrm{\prime }}\mathrm{.}$

This uses the same ordered-pair arc convention as a digraph in Multigraphs, loops and directed graphs as variants distinct from the default finite simple graph, but no finiteness claim is made here: the configuration graph may be infinite.

An accepting vertex is an accepting configuration of $N$.

• For a deterministic machine every nonhalting vertex has out-degree $1$, while for a nondeterministic machine it may have several outgoing arcs.

• The graph need not be acyclic. Looping computations and revisited configurations are part of the present scope.