Exercises — Turing machines — formal definition, computation, configurations

• A configuration $uqv$ = tape-left-of-head $u$, current state $q$, tape-from-head-onward $v$. The head sits on the first symbol of $v$.
• $C_1⊢C_2$ reads "$C_1$ yields $C_2$" — one application of the transition function $\delta$.
• $\delta (q,a)=(r,b,D)$ reads "in state $q$ reading $a$: go to state $r$, write $b$, move one cell in direction $D$ ($L$ = left, $R$ = right)".
• $\bigsqcup$ is the blank symbol; the tape is blank everywhere past the input.

In state $q_2$ with the head reading a 1: the machine (a) switches state to $q_5$, (b) overwrites that cell — the 1 becomes a 0, and (c) moves the head one cell right. All three happen in a single atomic step. The tape to the right of the head is untouched.

• $\Gamma$ (the tape alphabet) must contain $\bigsqcup$, because the infinite tape is blank past the input and the machine must be able to read that symbol.
• $\Sigma$ (the input alphabet) must not contain $\bigsqcup$ — that is how the machine tells "real input" from "empty tape". Also $\Sigma \subseteq \Gamma$.

True. When the right part $v$ is empty, the head has walked onto the blank region, so we treat it as $101q_7\bigsqcup$. The head reads $\bigsqcup$.

$q_{0}000⊢0q_{0}00⊢00q_{0}0⊢000q_0⊢000q_{\text{accept}}$

• Steps 1–3: each reads 0, writes 0 back, moves right — so one 0 moves from the right part into the left part each time.
• Step 4: the right part is empty ⇒ head reads $\bigsqcup$ ⇒ rule $\delta (q_0,\bigsqcup )$ fires ⇒ accept. Number of yield steps: 4.

$1q_3\#0⊢q_{5}1Y0$ We wrote Y over #, then moved left onto the 1. So the 1 becomes the new head symbol, and Y0 sits to its right. The head is now at cell 0 (the left edge).

The head is already at cell 0, and we are told to move $L$. By the left-edge convention the head stays put (there is no cell $-1$): $q_{5}1Y0⊢q_{6}1Y0$ The state changes to $q_6$, the 1 is rewritten as 1 (unchanged), but the head does not move.

Each step overwrites the current 0 with X and steps right: $q_{1}000⊢X{q}_{1}00⊢XX{q}_{1}0⊢XXX{q}_1$ After 3 steps the tape reads XXX, head over the blank past them. Result: XXX, head at cell 3 reading $\bigsqcup$.

Trace: $q_{0}00⊢0q_{0}0⊢00q_0$. Now the head reads $\bigsqcup$ and there is no transition defined. A partial $\delta$ with no rule for the current (state, symbol) means the machine halts with no move — and since it is not in $q_{\text{accept}}$, this counts as an implicit reject (by convention, an undefined transition sends the machine to $q_{\text{reject}}$). Answer: reject. (It does not loop — a missing rule is a halt, not an infinite run.)

Decidable (Turing-decidable / recursive). A TM that recognizes $L$ and halts on every input is a decider: for members it says yes, for non-members it says no, and it never loops. Decidable is strictly stronger than merely recognizable; every decidable language is recursive. The "halts on every input" clause is exactly what upgrades recognition to decision.

A recognizer only promises: if $w\in L$, then $M$ eventually enters $q_{\text{accept}}$. For $w\notin L$, the definition places no bound on $M$'s behaviour — $M$ may run forever (loop). While it is still running, we cannot conclude "no", because it might accept on the very next step. That inability to ever commit to "no" is precisely the recognizable-but-not-decidable gap; the Halting Problem shows this gap is real and unavoidable.

0000 (length 4 = $2^2$):

• Pass 1: 4 zeros → cross every other → 2 zeros left (even, $>1$). Continue.
• Pass 2: 2 zeros → cross every other → 1 zero left. Accept (base case $2^0=1$). ✓

000000 (length 6, not a power of two):

• Pass 1: 6 zeros → 3 zeros left (odd, $>1$). An odd count $>1$ cannot be halved evenly ⇒ reject. ✗

0000 is accepted; 000000 is rejected.

Idea: walk right to the first blank, remembering the last non-blank symbol in the state.

• $\delta (q_0,a)=(q_a,a,R)$ — saw an a, remember "last was a".
• $\delta (q_0,b)=(q_b,b,R)$ — saw a b, remember "last was b".
• $\delta (q_a,a)=(q_a,a,R)$, $\delta (q_a,b)=(q_b,b,R)$ — update memory.
• $\delta (q_b,a)=(q_a,a,R)$, $\delta (q_b,b)=(q_b,b,R)$.
• $\delta (q_b,\bigsqcup )=(q_{\text{accept}},\bigsqcup ,R)$ — reached end, last symbol was b ⇒ accept.
• $\delta (q_a,\bigsqcup )=(q_{\text{reject}},\bigsqcup ,R)$ — last was a ⇒ reject.
• $\delta (q_0,\bigsqcup )=(q_{\text{reject}},\bigsqcup ,R)$ — empty input has no last b ⇒ reject.

Halts on all inputs: the head only ever moves right and the input is finite, so it reaches the trailing blank after $|w|$ steps and halts. This is a genuine decider — no state loops in place. (A plain DFA could also do this; the TM just proves it lies inside the decidable class.)

Add a first-symbol gate using the start state $q_0$:

• $\delta (q_0,b)=(q_{\text{reject}},b,R)$ — starts with b ⇒ reject immediately.
• $\delta (q_0,a)=(q_a,a,R)$ — starts with a, now behave as before (need to end in b).
• $\delta (q_0,\bigsqcup )=(q_{\text{reject}},\bigsqcup ,R)$ — empty ⇒ reject.
• Then reuse $q_a,q_b$ rules from Ex 4.1 to track the last symbol, accepting only via $\delta (q_b,\bigsqcup )$.

Now the machine accepts exactly $\{axb:x\in \{a,b{\}}^{\ast }\}\cup \{ab\}$-style strings — starts with a, ends with b, length $\ge 2$. Still halts in $|w|$ steps (right-only motion).

$q_{0}ab⊢a{q}_{a}b⊢ab{q}_b⊢ab{q}_{\text{accept}}$

• Step 1: read a, write a, go $q_a$, move right.
• Step 2: read b, write b, go $q_b$, move right.
• Step 3: read $\bigsqcup$ (empty right part), rule $\delta (q_b,\bigsqcup )$ ⇒ accept. 3 yield steps; accepts.

Let $M$ be a decider for $L$: it halts on every input and accepts iff $w\in L$. Build $M^{\prime }$ identical to $M$ except swap the two halting states: wherever $M$ enters $q_{\text{accept}}$, $M^{\prime }$ enters $q_{\text{reject}}$, and vice-versa. Since $M$ halts on every input, so does $M^{\prime }$ (same steps, same halting point). And $M^{\prime }$ accepts $w$ $⟺$ $M$ rejects $w$ $⟺$ $w\notin L$ $⟺$ $w\in \overline{L}$. Thus $M^{\prime }$ decides $\overline{L}$, so $\overline{L}$ is decidable. $■$ Note: this swap trick fails for mere recognizers — swapping states does not turn a loop into a halt, so recognizable languages are not closed under complement.

False. A counting argument: there are only countably many Turing machines (each is a finite string over a finite description alphabet), hence only countably many recognizable languages. But the set of all languages over $\{0,1\}$ is the power set of $\{0,1{\}}^{\ast }$, which is uncountable (Cantor). Uncountably many languages cannot be covered by countably many machines, so most languages are not even recognizable. The Church–Turing thesis tells us "computable" = "TM-computable", so these languages are genuinely beyond any algorithm.

($\Rightarrow$) If $L$ is decidable, its decider recognizes $L$; by Ex 5.1 $\overline{L}$ is decidable too, hence recognizable. So both are recognizable.

($\Leftarrow$) Suppose $M_1$ recognizes $L$ and $M_2$ recognizes $\overline{L}$. Build $M$ that on input $w$ runs $M_1$ and $M_2$ in parallel (dovetailing: one step of each, alternately, using multiple tapes). Every $w$ is in exactly one of $L,\overline{L}$, so exactly one of $M_1,M_2$ will accept — and it does so in finitely many steps. When $M_1$ accepts, $M$ accepts; when $M_2$ accepts, $M$ rejects. Since one of them must halt-accept, $M$ always halts ⇒ $M$ is a decider ⇒ $L$ is decidable. $■$

A TM step does three things at once: change state, write a symbol, and move one cell L or R. Decidable ::: recognized by a TM that halts on every input. Recognizable but not decidable gap ::: the machine may loop forever on non-members. Complement of a decidable language ::: also decidable (swap accept/reject states). Why not every language is recognizable ::: countably many TMs, uncountably many languages.