Is there an undecidable finite language of finite words?

Question

Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$. Is it possible for $L'$ to be an undecidable language?

I see that there is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to establish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation. The aim is to find undecidability language without needing an infinite set, but I can't see it.

EDIT Note:

Although I chose an answer, many answers and all comments are important.

Answer 1

Yes, there is a need for $L$ to be infinite in order to be undecidable.

To add up on the answers of Raphael and Sam, you should think about "decidable" as things that a computer-program can solve. The program required is very simple, it just needs to output "Yes" for elements in $L$, or otherwise, say no.

So the more "complex" $L$ is, the longer the program you are required to write. In other words, the longer the program you run, you can check more things... So if someone gives a language $L$ which is finite, say $L=\{ a_1, a_2, \ldots, a_n\}$, you can write the following program:

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

Now, if some one gives you a larger $L$ (yet finite), you will just write a longer program. This is always true, and any finite $L$ will have it's own program. The only "interesting" case is what happens when $L$ is infinite - your program cannot be infinite.

The issue of "undecidability" is even more interesting: its those (infinite) $L$'s that have no program that works correctly for them. We know that such languages must exists since there are way more (infinite) languages $L$ than the number of programs of finite (but unbounded) length.

Answer 2

I'm not sure I understand the question properly but every finite language is regular. There are no regular languages which are undecidable and therefore there are no finite languages which are undecidable. All of these statements are well-known and proofs can be found in Hopcroft and Ullman.

Answer 3

If your language $L'$ is finite, you can perform table lookup on a hardcoded table containing all words in $L'$. This is awkward to write down as Turing machine, but in other, equivalent models that is quite clear.

In fact, finite automata are sufficient. Construct an automaton for $L'$ as follows:

1. For every $w \in L'$, create a linear chain of states that accepts $w$.
2. Create a new initial state $q_0$.
3. Connect $q_0$ to the initial states of all automata constructed in 1. with $\varepsilon$-transitions.

The thus constructed automaton obviously accepts $L'$. Therefore, $L'$ is regular and therewith computable (by $\mathrm{REG} \subsetneq \mathrm{RE}$).

Note that the some reasoning applies for co-finite $L'$, that is $\big|\overline{L'}\big| < \infty$; you just hardcode the elements not in $L'$.

Answer 4

To be at all interesting (for the purpose of thinking about computability) a decision problem has to have infinitely many "yes" answers and infinitely many "no" answers. Such decision problems correspond exactly to languages contain infinitely many strings over their alphabet and also exclude infinitely many strings over their alphabet.

Anything else is trivially able to be encoded in only a finite amount of information (at worst simply a big list of strings either in or not in the language), and therefore computable by simple DFAs / regular expressions. I would hope it should be obvious that for any finite list of strings you can immediately write down a regular expression that simply ORs all of the strings.

A witticism of my Theory of Computation lecturer was that the problem of "does God exist?" is computable - it is either computed by a machine that immediately accepts, or a machine that immediately rejects; we just don't know which one!