Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
There seem to be (at least) three questions here. Please concentrate on one and edit out the others. –  Raphael May 22 '12 at 13:31
    
I removed the references to the power set as it is not relevant here; $\mathcal{P}(S)$ is finite if and only if $S$ is finite. –  Raphael May 22 '12 at 13:51
    
@Raphael It's ok, but I mention power set because sometimes I read "there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language." I would like to understand why that didn't work with a finite set $L'$, with $|L'|\leq N$ with $N$ finite, instead of needing $\mathbb{N}$, that's why I put $\mathcal{P}(S)$ –  Hernan_eche May 22 '12 at 13:58
1  
As far as I know, the existence of undecidable languages does not follow immediately from the nonexistence of such a surjection; you need some tiny bits more. Why, that would make another wonderful question! Why don't you go ahead and ask it? From that one, you should see why the argument does not carry over to finite languages. –  Raphael May 22 '12 at 14:00
3  
Finite language are decidable, period, end of story. There are any number of algorithms for that. If you insist on the classical Turing Machine model, it can be done that way too, though less perspicaciously. No need to invoke finite-state automata or regular languages or any other automaton model, as they are in fact, overkill without any additional clarity vis-a-vis Turing Machines. –  David Lewis May 22 '12 at 14:10
show 6 more comments

4 Answers

up vote 8 down vote accepted

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.

share|improve this answer
    
+1 This is a very clear answer, I'd like you to expand a point, you've said "if some one fives you a larger $L$(yet finite), you will just write a longer program"* but I think the opposite, given a **fixed** finite set $P$ of programs $|P|=K$, what if you can't write a longer program I think some imputs $\in L$ a finite set, will out YES, and some won't. As $\mathcal{P}(P) \gt K$, then some of the imputs $\in L$ will correspond to indicator functions $P$ but *most won't!,because $2^K$ possible languages $\gt K$ possible programs, then there will be undecidable problems. Am I wrong? why? –  Hernan_eche May 23 '12 at 12:03
1  
indeed, if you limit the size of the program to $|P|=k$ then there are at most $O(2^k)$ different programs which correctly classify at most $O(2^k)$ different languages (infinite or not). So for that specific set of programs there exists undecidable languages and even a finite one. But this is a weaker statement, since you consider only a limited set of programs (e.g., $|P|=1$, you have only 2 possible programs; of course they will not be able to do much and will fail on almost every language $L$) –  Ran G. May 23 '12 at 16:38
    
thanks, I know that's a weaker statement, but it's bold that there could be finite and infinite Undecidable Languages, and I think this special case must be included in your answer, the parte "Yes, there is a need for L to be infinite in order to be undecidable." seems not to be a need under certain conditions. –  Hernan_eche May 23 '12 at 18:12
4  
Not exactly. The term "undecidable" has a specific meaning: not decidable by a standard Turing machine. Thus, to be undecidable, $L$ must be infinite. What you want is not undecidable but a different term, namely, "not decidable by $P$". Call the latter $P$-undecidable. Then there for any finite $P$, there is no need for $L$ to be infinite in order to be $P$-undecidable. Just don't confuse (or misuse) undecidable and $P$-undecidable –  Ran G. May 24 '12 at 4:37
add comment

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.

share|improve this answer
add comment

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'$.

share|improve this answer
add comment

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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