# Does there exist a undecidable infinite language with only a finite undecidable subset?

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

• No. You can correct such a decider to an actual decider by hardwiring the answer for the MAYBE elements. – 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.

• 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. – orlp Nov 27 '20 at 12:27
• 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? – orlp Nov 27 '20 at 12:30
• This is a common misconception. See for example this question. – Yuval Filmus Nov 27 '20 at 13:13
• @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. – Noah Schweber Dec 7 '20 at 7:20