Problem Detail: Is there a need for $Lsubseteq Sigma^*$ to be infinite to be undecidable? I mean what if we choose a language $L’$ be a bounded finite version of $Lsubseteq 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.
Asked By : Hernan_eche
Answered By : Ran G.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1990