= Solution
Fix a deterministic, single-tape <Turing machine> with tape cells indexed by the <integers>. A precise definition is the <tuple>
$$
M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}),\qquad
\delta:(Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gamma
\longrightarrow Q\times\Gamma\times\{L,R\}.
$$
Here $Q$ is a nonempty <finite set> of control states, $\Gamma$ a finite tape <alphabet> with a designated <blank symbol> $\square$, $\Sigma\subseteq\Gamma\setminus\{\square\}$ the input <alphabet>, $q_0\in Q$ the initial control state, and $q_{\mathrm{acc}},q_{\mathrm{rej}}\in Q$ distinct halting control states. The transition <function> is total on the displayed domain. The <Turing machine instruction> $\delta(q,a)=(r,b,D)$ means to write $b$ over the scanned $a$, enter control state $r$, and move the head one cell in direction $D$.
A <Turing machine configuration> is $(q,\tau,h)$, where $q\in Q$, $h\in\mathbb Z$ is the head position, and $\tau:\mathbb Z\to\Gamma$ is the tape-content <function>, equal to $\square$ outside a <finite set>. Its <next-configuration relation> is
$$
(q,\tau,h)\vdash_M(r,\tau',h+d)
$$
if $\delta(q,\tau(h))=(r,b,D)$, with $d=-1$ for $D=L$ and $d=1$ for $D=R$, and
$$
\tau'(j)=\begin{cases}b&j=h,\\\tau(j)&j\ne h.\end{cases}
$$
There is no successor to either halting <Turing machine configuration>.
For input $w=a_0\cdots a_{n-1}$, the initial <Turing machine configuration> is $C_0(w)=(q_0,\tau_w,0)$, where $\tau_w(j)=a_j$ for $0\leq j<n$ and is blank elsewhere. In particular, the initial tape for the <empty word> is entirely blank. The recognized <formal language> is
$$
\boxed{L(M)=\{w\in\Sigma^*:C_0(w)\vdash_M^*(q_{\mathrm{acc}},\tau,h)
\text{ for some }\tau,h\}.}
$$
The relation $\vdash_M^*$ permits any finite number of transitions. An input outside $L(M)$ may reach the rejecting control state or run forever; recognition does not require halting on every input.
Back to article page
