Question

This question already has an answer here:

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$?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top