Finite languages are Turing decidable - contradiction [duplicate]

Question

Let's say that I define the language $L$ over the alphabet $\{0, 1\}$ to be a language containing only one word, $w$, where:

$$ w = \begin{cases} 1 & \text{if the continuum hypothesis is true}\\ 0 & \text{otherwise.} \end{cases} $$

$L$ is finite, therefore there is a Turing Machine which can decide whether or not the word $1$ is in $L$. On contrary, continuum hypothesis is independent of $ZFC$, which means that it cannot be proven nor disproved from the standard Zermelo–Fraenkel set theory. As a consequence, we cannot know if $1$ or $0$ is in $L$. Then, how can we build a Turing Machine which can decide $L$?

Answer 1

This has been asked before in various guises. The answer is very simple.

If the continuum hypothesis holds, then here is pseudocode for a Turing machine accepting $L$:

• Accept if the input equals 1.

If the continuum hypothesis doesn't hold, then here is pseudocode for a Turing machine accepting $L$:

• Accept if the input equals 0.

In both cases, we have shown that there exists a Turing machine that decides $L$.

---

If you're confused, here is a slightly more formal version of your theorem:

There exists a Turing machine $T$ such that if CH holds, $L(T) = \{1\}$, and if CH doesn't hold, $L(T) = \{0\}$.

Since CH either holds or doesn't hold, one of the following machines accepts $L$: the machine accepting only $1$, and the machine accepting only $0$. In particular, there exists a Turing machine whose language satisfies the requirements.

---

Perhaps you're confused about the incompleteness result. It states that there is no proof in ZFC of the continuum hypothesis or of its negation. Nevertheless, the continuum hypothesis is either true or false.

More formally, we can think of it in the following way. We live in a "model" of ZFC (model is actually a formal term!), in which every statement (more accurately, every first-order statement in the language of ZFC) has a definite truth value. In particular, in our model either the continuum hypothesis is true or it is false, and we know for sure that one of the possibilities holds, even if we cannot prove either possibility (and so we don't know which one holds).

---

If you don't like this sort of reasoning, I suggest looking into constructive mathematics and intuitionism, which is what logicians who didn't like this kind of reasoning came up with.