Exercise 3

\[% Shared mathematical notation for CSC438. % % Keep this file limited to commands supported by both LaTeX and MathJax. % Quarto loads it through filters/shared-macros.lua; TeX preambles can use % \input{../macros} when compiled from a first-level project directory. \renewcommand{\subset}{\subseteq} \renewcommand{\iff}{\leftrightarrow} \newcommand{\N}{\mathbb{N}} \newcommand{\proves}{\vdash} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cP}{\mathcal{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\TR}{\mathbf{TR}} \newcommand{\D}{\mathbf{D}} \newcommand{\R}{\mathbb{R}} \newcommand{\seq}{\Rightarrow} \newcommand{\RA}{\Longrightarrow} \newcommand{\LRA}{\Longleftrightarrow} \newcommand{\OI}{\{0,1\}} \renewcommand{\SS}{\Sigma^*} \newcommand{\powerset}{\mathcal{P}} \newcommand{\blank}{\sqcup} \newcommand{\angles}[1]{\left\langle #1\right\rangle} \newcommand{\enc}[1]{\left\ulcorner #1\right\urcorner} \newcommand{\Lang}{\mathcal{L}} \newcommand{\Th}{\operatorname{Th}} \newcommand{\Thm}{\operatorname{Thm}} \newcommand{\Prov}{\operatorname{Prov}} \newcommand{\Con}{\operatorname{Con}} \newcommand{\ATM}{A_{\mathrm{TM}}} \newcommand{\HALTTM}{\operatorname{HALT}_{\mathrm{TM}}} \newcommand{\HALTe}{\operatorname{HALT}_{\epsilon}} \newcommand{\AExp}{A_E} \newcommand{\AMult}{A_M} \newcommand{\green}[1]{\textcolor{green}{#1}} \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\st}[1]{\sout{#1}} \]

1 Properties of Reductions

Recall that \(A \leq_m B\) means that there is a total computable function \(f : \Sigma^* \to \Sigma^*\) such that

\[ x \in A \iff f(x) \in B \]

for every \(x \in \Sigma^*\).

1.1

Show that if \(A \leq_m B\) and \(A\) is not recognizable, then \(B\) is not recognizable. We proved the analogous result for decidability in class.

Solution

Let \(f\) be a mapping reduction from \(A\) to \(B\). We prove the contrapositive: if \(B\) is recognizable, then \(A\) is recognizable.

Suppose \(M_B\) recognizes \(B\). Construct a machine \(M_A\) as follows:

M_A on input x:
    compute f(x)
    run M_B on f(x)
    if M_B accepts:
        accept

Because \(f\) is total and computable, the first step always halts. Moreover,

\[ x \in A \iff f(x) \in B. \]

If \(x \in A\), then \(M_B\) eventually accepts \(f(x)\), so \(M_A\) accepts \(x\). If \(x \notin A\), then \(M_B\) never accepts \(f(x)\), so \(M_A\) does not accept \(x\). Thus, \(M_A\) recognizes \(A\).

Therefore, if \(A\) is not recognizable, then \(B\) cannot be recognizable.

1.2

Prove that if \(A \leq_m B\), then \(\overline{A} \leq_m \overline{B}\).

Solution

Let \(f\) be a mapping reduction from \(A\) to \(B\). The same function \(f\) is a mapping reduction from \(\overline{A}\) to \(\overline{B}\). Indeed, for every \(x\),

\[ \begin{aligned} x \in \overline{A} &\iff x \notin A \\ &\iff f(x) \notin B \\ &\iff f(x) \in \overline{B}. \end{aligned} \]

The function \(f\) is still total and computable, so \(\overline{A} \leq_m \overline{B}\).

1.3

Prove that \(\leq_m\) is transitive. That is, if \(A \leq_m B\) and \(B \leq_m C\), then \(A \leq_m C\).

Solution

Let \(f\) be a mapping reduction from \(A\) to \(B\), and let \(g\) be a mapping reduction from \(B\) to \(C\). Define

\[ h(x) = g(f(x)). \]

Because \(f\) and \(g\) are total and computable, their composition \(h\) is also total and computable. Furthermore, for every \(x\),

\[ x \in A \iff f(x) \in B \iff g(f(x)) \in C \iff h(x) \in C. \]

Therefore, \(h\) is a mapping reduction from \(A\) to \(C\), and hence \(A \leq_m C\).

2 Rice’s Theorem

Think of a property \(P\) as a function from \(\Sigma^*\) to \(\{\text{True},\text{False}\}\). A string \(x\) has property \(P\) if \(P(x)=\text{True}\).

• A property is nontrivial if there exist \(x,y \in \Sigma^*\) such that \(P(x)=\text{True}\) and \(P(y)=\text{False}\). In other words, \(P\) is neither always true nor always false.
• A property is semantic if it depends only on \(\cA(M_x)\). That is, \(\cA(M_x)=\cA(M_y)\) implies that \(P(x)=P(y)\). If two strings describe Turing machines that accept the same language, then either both strings have the property or neither does.

For example, the properties “\(\cA(M_x)\) is empty,” “\(\cA(M_x)\) is finite,” and “\(\cA(M_x)\) contains \(010\)” are semantic. By contrast, “\(M_x\) has at most ten states” is a property of the machine’s description, so it is not semantic.

For each property \(P\), define

\[ R_P = \{x : P(x)=\text{True}\}. \]

Rice’s theorem states that if \(P\) is nontrivial and semantic, then \(R_P\) is undecidable.

2.1

Prove Rice’s theorem by reducing from \(\ATM\).

TipHint

It may be useful to begin with the case in which \(P\) does not hold for an encoding of a Turing machine that always rejects.

Prove this case first, and then adapt your argument to the case in which \(P\) does hold for such an encoding.

Solution

Let \(M_{\bot}\) be a Turing machine that always rejects.

Following the hint, first suppose that \(P(\angles{M_{\bot}})=\text{False}\). By nontriviality, there is some \(y\) such that \(P(y)=\text{True}\).

We show that \(\ATM \leq_m R_P\).

Map \(\angles{M,w}\) to the encoding of the following Turing machine \(N\):

N(z):
    simulate M on w
    if M accepts w:
        simulate M_y on z
    if M rejects w:
        reject

If \(\angles{M,w} \in \ATM\), then \(\cA(N)=\cA(M_y)\). Because \(P\) is semantic and \(P(y)=\text{True}\), we have \(\angles{N} \in R_P\).

On the other hand, if \(\angles{M,w} \notin \ATM\), then \(N\) accepts no inputs: it rejects every input if \(M\) rejects \(w\) and loops on every input if \(M\) loops on \(w\). Hence,

\[ \cA(N)=\emptyset=\cA(M_{\bot}), \]

so \(\angles{N} \notin R_P\). Thus,

\[ \angles{M,w} \in \ATM \iff \angles{N} \in R_P. \]

The map from \(\angles{M,w}\) to \(\angles{N}\) is total and computable, so \(\ATM \leq_m R_P\). Therefore, \(R_P\) is undecidable.

Now suppose that \(P(\angles{M_{\bot}})=\text{True}\). Consider the opposite property \(\overline{P}\), defined by \(\overline{P}(x)=\text{True}\) exactly when \(P(x)=\text{False}\). The property \(\overline{P}\) is nontrivial and semantic, and it does not hold for \(\angles{M_{\bot}}\). By the preceding argument, \(R_{\overline{P}}=\overline{R_P}\) is undecidable. If \(R_P\) were decidable, then its complement would also be decidable. Therefore, \(R_P\) is undecidable.

3 Some More Languages

Define the following languages:

\[ \begin{aligned} E_{\mathrm{TM}} &= \{x : \cA(M_x)=\emptyset\}, \\ \operatorname{ALL}_{\mathrm{TM}} &= \{x : \cA(M_x)=\Sigma^*\}, \\ \operatorname{EQ}_{\mathrm{TM}} &= \{\angles{x, y} : \cA(M_x)=\cA(M_y)\}. \end{aligned} \]

For each language and its complement, determine whether it is decidable, recognizable but undecidable, or not recognizable. Justify each answer and use whatever method you want.

Solution

The classifications are:

Language	Classification
\(E_{\mathrm{TM}}\)	Not recognizable
\(\overline{E_{\mathrm{TM}}}\)	Recognizable but undecidable
\(\operatorname{ALL}_{\mathrm{TM}}\)	Not recognizable
\(\overline{\operatorname{ALL}_{\mathrm{TM}}}\)	Not recognizable
\(\operatorname{EQ}_{\mathrm{TM}}\)	Not recognizable
\(\overline{\operatorname{EQ}_{\mathrm{TM}}}\)	Not recognizable

The language \(\overline{E_{\mathrm{TM}}}\) is recognizable. Let \(G\) be an enumerator for \(\Sigma^* \times \N\), constructed in the preceding enumeration exercises.

not_empty(x):
    for (w, k) in G:
        simulate M_x on w for k steps
        if accepted: accept

If \(\cA(M_x)\) is nonempty, then \(M_x\) accepts some string \(w\) within some number of steps, say \(k\). The pair \((w,k)\) is eventually printed by \(G\), so the program above accepts \(x\).

The property of recognizing the empty language is nontrivial and semantic, so \(E_{\mathrm{TM}}\) is undecidable by Rice’s theorem. If \(E_{\mathrm{TM}}\) were also recognizable, then both it and its complement would be recognizable, making it decidable. This is a contradiction. Therefore, \(E_{\mathrm{TM}}\) is not recognizable, while \(\overline{E_{\mathrm{TM}}}\) is recognizable but undecidable.

---

\(\operatorname{ALL}_{\mathrm{TM}}\) is not recognizable. We show this by reducing from \(\overline{A_{\mathrm{TM}}}\). Given \(\angles{M,w}\), construct a machine \(N\) that behaves as follows:

N(z):
    simulate M on w for |z| + 1 steps
    if M accepts within that time:
        reject
    otherwise:
        accept

If \(M\) never accepts \(w\), then \(N\) accepts every input, so \(\cA(N)=\Sigma^*\). If \(M\) accepts \(w\) after \(t\) steps, then \(N\) rejects every sufficiently long string, so \(\cA(N) \neq \Sigma^*\). Thus,

\[ \angles{M,w} \in \overline{A_{\mathrm{TM}}} \iff \angles{N} \in \operatorname{ALL}_{\mathrm{TM}}. \]

Because \(\overline{A_{\mathrm{TM}}}\) is not recognizable, \(\operatorname{ALL}_{\mathrm{TM}}\) is not recognizable.

To show that \(\overline{\operatorname{ALL}_{\mathrm{TM}}}\) is not recognizable, we again reduce from \(\overline{\ATM}\). Given \(\angles{M,w}\), construct \(N'\) as follows:

N' on input z:
    simulate M on w
    if M accepts:
        accept
    if M rejects:
        reject

If \(M\) accepts \(w\), then \(N'\) accepts every input. If \(M\) does not accept \(w\), then \(N'\) accepts no inputs.

Therefore,

\[ \angles{M,w} \in \overline{A_{\mathrm{TM}}} \iff \angles{N'} \in \overline{\operatorname{ALL}_{\mathrm{TM}}}. \]

Since \(\overline{A_{\mathrm{TM}}}\) is not recognizable, \(\overline{\operatorname{ALL}_{\mathrm{TM}}}\) is not recognizable.

---

We now show \(\operatorname{EQ}_{\mathrm{TM}}\) is not recognizable by reduction from \(\operatorname{ALL}_{\mathrm{TM}}\).

Let \(M_{\mathrm{all}}\) be a machine that accepts every input. Map an encoding \(\angles{M}\) to the pair \(\angles{M,M_{\mathrm{all}}}\). Then

\[ \angles{M} \in \operatorname{ALL}_{\mathrm{TM}} \iff \angles{M,M_{\mathrm{all}}} \in \operatorname{EQ}_{\mathrm{TM}}. \]

Thus, \(\operatorname{ALL}_{\mathrm{TM}} \leq_m \operatorname{EQ}_{\mathrm{TM}}\). Because \(\operatorname{ALL}_{\mathrm{TM}}\) is not recognizable, \(\operatorname{EQ}_{\mathrm{TM}}\) is not recognizable.

By Problem 1.2, we also have \(\overline{\operatorname{ALL}_{\mathrm{TM}}} \leq_m \overline{\operatorname{EQ}_{\mathrm{TM}}}\). Since \(\overline{\operatorname{ALL}_{\mathrm{TM}}}\) is not recognizable, \(\overline{\operatorname{EQ}_{\mathrm{TM}}}\) is also not recognizable.