There are problems a computer can't solve?

Let $S$ be the set described in the problem. If $L$ is a subset of natural numbers, denote its complement by $L^c$ . Note the trivial identity $(L^c)^c = L$ .

If $L$ is a subset of natural numbers, we have the following results:

1. $S^c$ is semi-decidable but not decidable.
2. If $L$ is decidable then $L$ is semi-decidable.
3. If $L, L^c$ are semi-decidable then $L$ is decidable.

We will first show that these results are sufficient.

Using Result 1, we know that $S^c$ is semi-decidable, but not decidable. Using Result 3 with $L = S^c$ , since $S^c$ is not decidable, "both $S^c, (S^c)^c = S$ are semi-decidable" must be wrong, so one of them must be not semi-decidable. However, $S^c$ is semi-decidable, so the only option is for $S$ to be not semi-decidable. Using Result 2, since $S$ is not semi-decidable, $S$ is not decidable either. This gives the answer not decidable, not semi-decidable .

We will now prove the individual results. Before that, we have a few conventions, however.

• We assume that the input to an algorithm is a natural number. (More commonly this input is a binary string, but simply tack on a $1$ at the front and interpret it as a binary number (and subtract by $1$ if you start counting from $0$ ) to make it a natural number.)
• Running an algorithm $A$ on input $x$ will be written as $A(x)$ .
• An algorithm $A$ decides a set $L$ if for every natural number $x$ , $A(x)$ halts and outputs "yes" (or $1$ ) if $x \in L$ , while $A(x)$ halts and outputs "no" (or $0$ ) if $x \not\in L$ . Note that there exists an algorithm that decides $L$ if and only if $L$ is decidable.
• Likewise, an algorithm $A$ semi-decides a set $L$ if for every natural number $x$ , $A(x)$ halts if $x \in L$ (we don't care about the output), while $A(x)$ doesn't halt if $x \not\in L$ (and clearly cannot output anything). Note that there exists an algorithm that semi-decides $L$ if and only if $L$ is semi-decidable.

---

Result 1 : $S^c$ is semi-decidable but not decidable.

To prove this, we return back to the algorithmic definition. Suppose $A$ is an algorithm, and we want to check whether $A \in S^c$ .

Checking that $S^c$ is semi-decidable is quite simple. We require that for some input $x$ , $A(x)$ halts. Thus we can simply simulate all the inputs; if any of them halts, we're done. The problem, however, lies in how we simulate them: if we simulate the input one by one, if we get to a non-halting input we can never know whether to stop simulating or to decide to move to the next input, while if we simulate all inputs simultaneously, this requires infinite memory.

A simple approach is thus to simulate $A$ on inputs $1, 2, \ldots, N$ for $N$ steps each; if none of them halts, increase $N$ and redo the whole thing. This guarantees that we will sooner or later stumble on a halting simulation, if there is any: if $A$ halts on input $p$ for $q$ steps, then when we arrive at $N = \max \{p,q\}$ , we will find that one of our simulations halts and thus we get $A \in S^c$ . If $A$ never halts for any input, then no simulation will halt before $N$ steps for any $N$ , so $A$ will keep running by increasing $N$ larger and larger.

Proving that $S^c$ is not decidable is similar to proving that halting problem is not decidable. Suppose there exists an algorithm $B$ that decides $S^c$ . Construct an algorithm $C$ as follows:

• Run $B$ with input $C$ .
• If the result is "yes", then loop forever. If the result is "no", then halt.

Note that $C$ ignores the input, thus there are only two possible cases:

• $B(C)$ gives answer "yes". Since $C$ ignores its output, this means $C$ halts. But then $C$ will loop forever from the second step, contradiction.
• $B(C)$ gives answer "no". Again, since $C$ ignores its output, this means $C$ runs forever. But then $C$ will halt from the second step, contradiction as well.

This implies a contradiction, so such algorithm $B$ cannot exist. $S^c$ is not decidable after all.

Result 2 : If $L$ is decidable then $L$ is semi-decidable.

Suppose an algorithm $A$ decides $L$ . Then construct algorithm $B$ simply by running $A$ (on the same input), and if the answer is "no", continuing by looping forever. This algorithm can be easily seen to semi-decide $L$ . If $x \in L$ , $A(x)$ returns "yes" and thus $B(x)$ halts, while if $x \not\in L$ , $A(x)$ returns "no" and thus $B(x)$ doesn't halt. Since there is an algorithm that semi-decides $L$ , this proves that $L$ is semi-decidable.

Result 3 : If $L, L^c$ are semi-decidable then $L$ is decidable.

Since $L, L^c$ are semi-decidable, there exist algorithms $A, A'$ where $A$ semi-decides $L$ and $A'$ semi-decides $L^c$ . Now construct an algorithm $B$ that simulates both $A$ and $A'$ (on the same input given to $B$ ) together, one step by one step, alternately. (That is, for input $x$ to $B$ , run one step of $A(x)$ , then one step of $A'(x)$ , then another step of $A(x)$ , then another step of $A'(x)$ , and so on; both are run in separate "environments", of course.) When a simulation halts, note which of $A(x), A'(x)$ is the one that halts; if it's $A(x)$ , then return "yes", otherwise return "no". Suppose $x \in L$ . Then, since $A$ semi-decides $L$ and $x \in L$ , we know that $A(x)$ will halt. Likewise, since $A'$ semi-decides $L^c$ and $x \not\in L^c$ , we know $A'(x)$ will not halt. Thus $B(x)$ will eventually halt (since it simulates $A(x)$ wholly), and when it halts, it will return "yes" (since it's $A(x)$ and not $A^c(x)$ that halts). A similar conclusion can be obtained when $x \not\in L$ . This proves that $B$ decides $L$ , which means $L$ is decidable.

Since we have proven the three requisite results, the proof is now complete.