Computable Reductions and Rice's Theorem

For reflexivity, use the identity map $\mathrm{id}(x)=x$ on $A$'s alphabet. It is total and computable, and $x\in A⟺\mathrm{id}(x)\in A$ for every $x$, so [L1] gives $A{\le }_{m}A$.

For transitivity, let $f$ witness $A{\le }_{m}B$ and let $g$ witness $B{\le }_{m}C$. By [L1], both maps are total and computable, so $h:=g\circ f$ is total and computable as well.

For every $x$, [L1] gives $x\in A⟺f(x)\in B⟺g(f(x))\in C$. Thus $x\in A⟺h(x)\in C$, so [L1] yields $A{\le }_{m}C$.

Let $f$ witness $A{\le }_{m}B$. By [L1], $f$ is total and computable and satisfies $x\in A⟺f(x)\in B$ for all $x$.

If $B$ is decidable, [L2] supplies a decider $D_B$ for $B$. On input $x$, first compute $f(x)$ and then run $D_B$ on that word. By step 1.1 the output is correct for $A$, and totality of $f$ and $D_B$ makes the composite machine halt on every input. Therefore $A$ is decidable.

If $B$ is recognizable, [L2] supplies a recognizer $R_B$ for $B$. On input $x$, compute $f(x)$ and run $R_B$ on it. By step 1.1 this machine accepts exactly the words of $A$, so $A$ is recognizable.

By [L2], $A_{TM}$ is recognizable. To use [L1], it remains to prove c.e.-hardness.

Let $L$ be any recognizable language, and choose a recognizer $R$ for $L$. Define $f(x):=⟨<mi\; mathvariant="normal">⌜</mi>R<mi\; mathvariant="normal">⌝</mi>,\widehat{x}⟩$. Because $R$ is fixed, encoding its chosen code and pairing it with the canonical word-code of $x$ is a total computable procedure. By [L3], $x\in L$ exactly when $R$ accepts $x$, and that happens exactly when $f(x)\in A_{TM}$. Thus $L{\le }_m{A}_{TM}$.

Step 1.2 proves that every recognizable language many-one reduces to $A_{TM}$, and step 1.1 already recorded recognizability. Therefore [L1] gives that $A_{TM}$ is c.e.-complete.

Let $f$ witness $A{\le }_{m}B$. Build an oracle machine that, on input $x$, first computes $f(x)$ and then asks the oracle for $B$ whether $f(x)\in B$.

By [L1], the oracle answer to step 1.1 is "yes" exactly when $x\in A$. The machine makes only that one query and then halts with the same answer, so [L2] shows that it is a Turing reduction from $A$ to $B$.

With oracle access to $A_{TM}$, an input $x$ belongs to $\overline{A_{TM}}$ exactly when the oracle answers "no" to the single query $x$. So the machine that asks that one query and flips the answer halts on every input and decides $\overline{A_{TM}}$. Hence $\overline{A_{TM}}{\le }_T{A}_{TM}$.

Suppose instead that $\overline{A_{TM}}{\le }_m{A}_{TM}$. Then $\overline{A_{TM}}$ would be recognizable because $A_{TM}$ is recognizable by [L1] and recognizability transfers backward along many-one reductions. Since [L1] also makes $A_{TM}$ recognizable, [L2] would imply that $A_{TM}$ is decidable, contradicting [L3]. Therefore $\overline{A_{TM}}\mathrm{̸}{\le }_m{A}_{TM}$.

Steps 1.1 and 1.2 exhibit a Turing reduction that is not a many-one reduction, so Turing reducibility is strictly weaker than computable many-one reducibility.

If $\mathrm{\varnothing }\mathrm{\notin }\mathcal{P}$, choose a recognizable language $W\in \mathcal{P}$. If instead $\mathrm{\varnothing }\in \mathcal{P}$, choose a recognizable language $W\mathrm{\notin }\mathcal{P}$. In either case, this choice fixes a recognizable language $W$ that lies on the opposite side of $\mathcal{P}$ from $\mathrm{\varnothing }$.

Fix a recognizer $R_W$ for $W$. For each coded pair $x=⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩$, build a machine $N_x$ that on input $y$ simulates $M$ on $w$; if that simulation ever accepts, $N_x$ starts a simulation of $R_W$ on $y$, and if the simulation of $M$ never accepts then $N_x$ never accepts $y$. Because the code of $R_W$ is fixed and $x$ is inserted as data, the map $x\mapsto <mi\; mathvariant="normal">⌜</mi>N_x<mi\; mathvariant="normal">⌝</mi>$ is total and computable.

If $x\in A_{TM}$, then [L2] says that $M$ accepts $w$, so step 2.1 eventually releases the simulation of $R_W$ on every input $y$; hence $L(N_x)=W$. If $x\mathrm{\notin }{A}_{TM}$, the simulation of $M$ on $w$ never accepts, so $N_x$ accepts no input and $L(N_x)=\mathrm{\varnothing }$. This is exactly the required witness-machine construction.

Assume for contradiction that $I_{\mathcal{P}}$ is decidable. Fix the map $g$ and the language $W$ from [L1]. Because $W$ and $\mathrm{\varnothing }$ lie on opposite sides of $\mathcal{P}$, exactly one of the two conditions $W\in \mathcal{P}$ and $\mathrm{\varnothing }\in \mathcal{P}$ holds.

On input $x$, compute $g(x)=<mi\; mathvariant="normal">⌜</mi>N_x<mi\; mathvariant="normal">⌝</mi>$ and run the assumed decider for $I_{\mathcal{P}}$ on that code. If $W\in \mathcal{P}$, answer exactly as the decider answers; if $\mathrm{\varnothing }\in \mathcal{P}$, flip the decider's answer. By [L1], this procedure accepts exactly those $x$ in $A_{TM}$, so it decides $A_{TM}$.

Step 2.1 contradicts [L2]. Therefore the assumption in step 1.1 was false, and $I_{\mathcal{P}}$ is undecidable.

Each listed property is extensional in the sense of [L2]: if two machines recognize the same language, then either both languages are empty, both are finite, both are regular, or both are context-free.

Each property is nontrivial. For emptiness, $\mathrm{\varnothing }$ belongs and $\{0\}$ does not. For finiteness, $\{0\}$ belongs and $\{0^n:n\ge 0\}$ does not. For regularity, $\mathrm{\varnothing }$ belongs and the standard recognizable language $\{0^n{1}^n:n\ge 0\}$ does not. For context-freedom, $\{0^n{1}^n:n\ge 0\}$ belongs and the standard recognizable language $\{0^n{1}^n{2}^n:n\ge 0\}$ does not.

Therefore [L1] applies to each of the four properties, so each corresponding index set is undecidable.

By [L2], $\overline{A_{TM}}$ is not recognizable: otherwise both $A_{TM}$ and its complement would be recognizable and hence $A_{TM}$ would be decidable.

Choose a recognizer for $A$, and let $\mathrm{\Sigma }$ be its finite input alphabet. Dovetail the recognizer on the words of ${\mathrm{\Sigma }}^{\ast }$ in a fixed length-lexicographic order, outputting each newly accepted word once. This gives an effective enumeration of $A$ by finite stages $F_0\subseteq F_1\subseteq \cdots$ with ${\bigcup }_s{F}_s=A$.

Suppose for contradiction that no finite subset of $A$ belongs to $\mathcal{P}$. For each binary word $x$, effectively construct a recognizer $N_x$ that, on its own input $y$, simulates the stage enumeration from step 1.2 and the recognizer for $A_{TM}$ on $x$ in lockstep. It accepts if $y$ appears in the stage enumeration before the latter recognizer accepts, and otherwise continues forever. The coding in [L3] makes $x\mapsto <mi\; mathvariant="normal">⌜</mi>N_x<mi\; mathvariant="normal">⌝</mi>$ total and computable. If $x\mathrm{\notin }{A}_{TM}$ then $L(N_x)=A\in \mathcal{P}$; if $x\in A_{TM}$ then $L(N_x)=F_s\mathrm{\notin }\mathcal{P}$ for the finite stage $s$ at which that simulation stops admitting new words.

A recognizer for $I_{\mathcal{P}}$ could therefore recognize $\overline{A_{TM}}$: on input $x$, compute $<mi\; mathvariant="normal">⌜</mi>N_x<mi\; mathvariant="normal">⌝</mi>$ and run the index-set recognizer on it. This contradicts step 1.1. Hence there is a finite set $F\subseteq A$ with $F\in \mathcal{P}$.

Let $B$ be recognizable with $F\subseteq B$, and suppose for contradiction that $B\mathrm{\notin }\mathcal{P}$. For each binary word $x$, effectively build a recognizer $K_x$ that accepts every word of $F$ and, if the recognizer for $A_{TM}$ accepts $x$, also simulates a fixed recognizer for $B$. Then $x\mathrm{\notin }{A}_{TM}$ gives $L(K_x)=F\in \mathcal{P}$, while $x\in A_{TM}$ gives $L(K_x)=F\cup B=B\mathrm{\notin }\mathcal{P}$. As in step 3.1, the total computable map $x\mapsto <mi\; mathvariant="normal">⌜</mi>K_x<mi\; mathvariant="normal">⌝</mi>$ and the recognizer for $I_{\mathcal{P}}$ would recognize $\overline{A_{TM}}$, contradicting step 1.1. Therefore every such $B$ belongs to $\mathcal{P}$, and $F$ is the required finite positive witness.

Adjoining any number of new states with no incoming transitions leaves every existing computation unchanged. Thus the original machine and the enlarged machine recognize the same language.

Start with a three-state machine and adjoin eight unreachable states. The two machines have the same recognized language by step 1.1, but the first has at most ten states and the second has eleven. Hence the state-count property is not extensional.

For the second property, take a three-state machine whose start state moves to its accept state on one input symbol and to its reject state on the blank symbol; each of its three states is reachable. Adjoin one state with no incoming transitions. Step 1.1 again preserves the recognized language, but now exactly the enlarged machine has an unreachable state. Hence this property is not extensional either.

Since the extensionality hypothesis of [L2] fails for both properties, Rice's theorem does not speak about them.

If $f$ is a many-one reduction from $A$ to $B$, then [L1] says that $x\in A$ and $f(x)\in B$ always have the same truth value. Equivalently, $x\mathrm{\notin }A⟺f(x)\mathrm{\notin }B$ as well.

So a valid reduction preserves both yes-answers and no-answers relative to the chosen target language $B$; it does not reverse them. Reversal would mean reducing to the complement language $\bar{B}$ instead. Therefore the statement is false.

By [L1], the property "has at most $k$ states" can change when one rewrites the machine without changing its recognized language. So it is not an extensional language property.

Because the extensionality hypothesis of [L2] fails, Rice's theorem does not apply to this property. Therefore the statement is false.