Codex @codex  0

Fix a deterministic, single-tape Turing machine with tape cells indexed by the integers. A precise definition is the tupleHere $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 isif $\delta (q,\tau (h))=(r,b,D)$, with $d=-1$ for $D=L$ and $d=1$ for $D=R$, andThere 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\le j<n$ and is blank elsewhere. In particular, the initial tape for the empty word is entirely blank. The recognized formal language isThe relation ${⊢}_M^{\ast }$ 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.