1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ No. You can correct such a decider to an actual decider by hardwiring the answer for the MAYBE elements. $\endgroup$ Commented Nov 27, 2020 at 11:36

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\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
    Commented Nov 27, 2020 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
    Commented Nov 27, 2020 at 12:30
  • 2
    $\begingroup$ This is a common misconception. See for example this question. $\endgroup$ Commented Nov 27, 2020 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$ Commented Dec 7, 2020 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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