I know that there's no such thing as a finitely sized undecidable language. However, does there exist an undecidable language where a finitely sized set of undecidable elements are 'hiding among' an infinite set of decidable elements?

In order to formalize this, let's build a deciding machine that answers $\text{YES}$, $\text{NO}$, or $\text{MAYBE}$. A correct decider for a language may always answer $\text{MAYBE}$, but if it answers $\text{YES}$ or $\text{NO}$ its answer must be correct. Such a decider can always be constructed for any (undecidable) language - in the worst case it simply always returns $\text{MAYBE}$.

Does there exist an undecidable language $L$ for which a correct decider exists that only answers $\text{MAYBE}$ for a finite number of elements of $L$?

  • 1
    $\begingroup$ No. You can correct such a decider to an actual decider by hardwiring the answer for the MAYBE elements. $\endgroup$ – Yuval Filmus Nov 27 '20 at 11:36

Let $S$ be the set of elements on which the decider $T$ answers MAYBE. We can construct a new decider $T'$ which correctly decides $L$ as follows:

  • If the input is in $S$, answer the hardwired correct answer.
  • Otherwise, run $T'$.

Hence $L$ is decidable.

This actually shows that if $L$ is undecidable, then every decider for $L$ must make infinitely many mistakes.

  • $\begingroup$ I'm not convinced by your answer because your construction assumes knowledge of $S$ during the construction (to allow for the hardwiring). However you did not give a terminating algorithm for finding $S$ given access to $T$, so your overall construction might not terminate. $\endgroup$ – orlp Nov 27 '20 at 12:27
  • $\begingroup$ To elaborate on a potential 'just enumerate all $S$ in $L$' rebuttal, even though $S$ is finite, $|S|$ is not given. How do you know you have hardcoded all exceptions and can return your new decider? $\endgroup$ – orlp Nov 27 '20 at 12:30
  • 2
    $\begingroup$ This is a common misconception. See for example this question. $\endgroup$ – Yuval Filmus Nov 27 '20 at 13:13
  • $\begingroup$ @orlp We can prove that such a machine exists - and this answers your question - even if we can't prove which specific machine does the job. $\endgroup$ – Noah Schweber Dec 7 '20 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.