Decidable, Recognizable, and Enumerable Languages: Examples and Counterexamples

A recognizer for $A$ scans the input from left to right and accepts as soon as it sees a 1; on an all-zero input it may simply continue forever. A recognizer for $A^c$ scans to the end of the input and accepts exactly when every scanned symbol is 0.

On any input word, exactly one of the two recognizers from step 1.1 eventually accepts. Therefore [L1] interleaves them into a decider for $A$.

The words 0 and 10 are malformed. The first never even begins the required positive-arity tuple code, and the second announces arity $1$ but provides no self-delimiting payload block. Therefore the decoder of [L1] rejects both.

The word 111111011011100101101100101 is the code of the tuple $(11,0,1,1,0,1)$, so it decodes to the normalized machine with $m=3$, $s=0$, $n=1$, and the unique transition $(0,0)\mapsto (1,0,1)$. In particular $0\le s<n$, and the tuple has the required $3+3(m-2)n=6$ entries. Thus [L1] accepts it as a well-formed machine description, and [L2] classifies the three sample words exactly as claimed.

This makes the decidability test concrete: two malformed inputs are rejected and one genuine machine code is accepted.

Let $M$ accept immediately on input 0 and otherwise move right forever without entering any halting state. Then [L1] shows that $M$ recognizes exactly $\{0\}$.

Every nonmember of $\{0\}$ makes $M$ diverge, so $M$ is not total. This contradicts the claim summarized in [L2].

Therefore $M$ is a concrete counterexample to the refuted statement.