4
$\begingroup$

From this statement

As 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 similar reasoning does not work with a finite set $B$ which also has no surjection onto $\mathcal{P}(B)$! (with $|B|=K$ and $K \in \mathbb{N}$)

Why is there a minimum need for the infinite set?

EDIT Note:

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

Improve this question
$\endgroup$
6
  • $\begingroup$ Where did the statement come from? Do you have a reference and/or proof of the statement? $\endgroup$
    – Sam Jones
    Commented May 22, 2012 at 14:25
  • $\begingroup$ @Sam Jones, do you think the statement isn't right? I think the statement is ok, it's from this answer: cs.stackexchange.com/a/468/1396 $\endgroup$
    – Hernan_eche
    Commented May 22, 2012 at 14:30
  • $\begingroup$ Oh, I see. It's about diagonalization... $\endgroup$
    – Sam Jones
    Commented May 22, 2012 at 14:31
  • 2
    $\begingroup$ I think the answer of your question is also contained in cs.stackexchange.com/a/468/1396 : "The reason is that the set of programs is equinumerous to $\mathbb{N}$" $\endgroup$
    – Marc Bury
    Commented May 22, 2012 at 14:40
  • 1
    $\begingroup$ The quoted statement without context is not terribly informative, which might be the reason for your problem. $\mathbb{N}$ there does not represent the undecidable language, but the set of all Turing machines. $\endgroup$
    – Raphael
    Commented May 22, 2012 at 14:48

2 Answers 2

Reset to default
6
$\begingroup$

If you take any finite set $A$ of TMs, there is a language not decided by any TM in $A$ and the finite powerset would suffice for that. But this is not what we want. We want to show that there is an undecidable language, i.e. a language that no TM can decide it. The cardinality difference between a finite set and its power set would not show that. You need the cardinality difference with the set of all TMs which is countable to say there is a language which is not decided by any machine in the set.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Simple and right to the point. $\endgroup$
    – David Lewis
    Commented May 22, 2012 at 18:35
  • $\begingroup$ @Kaveh Thanks for this answer, I understand this better, I think I've confused terms, about Undecidable Language, Undecidable Problem, it's really confusing universe, the set of functions, set of inputs, and so on, because in some way are interchangeable terms, in the sense that problems define functions, functions define acepted inputs, and they define languages, I am trying to understand this as much as I can, I've put a comment in Raphael answer because I still think that the no surjection means something for the finite case. $\endgroup$
    – Hernan_eche
    Commented May 22, 2012 at 19:37
  • $\begingroup$ @Hernan_e, yes, it happens to people new to computability theory, but the problem doesn't last long usually. $\endgroup$
    – Kaveh
    Commented May 24, 2012 at 0:29
6
$\begingroup$

Let us first recapitulate in which context the cited statement makes sense.

  1. Let us restrict ourselves to the domain of (decision) functions in $\mathbb{N} \to \{0,1\}$ (a subset of all functions).
  2. Every such function corresponds to one element of $\mathcal{P}(\mathbb{N})$ (see characteristic function).
  3. There are countably many Turing machines (simple encoding).

By 1. and 2., there are uncountably many functions. Therefore, there are functions that have no corresponding Turing machine, that is they are not computable. There are simply too many functions; this is what is meant by "there is no surjection".

Now, there are only countably many finite sets in $\mathcal{P}(\mathbb{N})$(extension of Cantor's pairing function). Therefore, the same contradiction can not be derived when only considering finite sets.

If you add some infinite sets to your base set so it becomes uncountable, there is no reason to believe some of the finite sets were undecidable; you only know that there are some undecidable sets. In fact, all finite sets are decidable, so the culprits are always infinite sets.

Improve this answer
$\endgroup$
6
  • $\begingroup$ If you avoid using infinite $\mathbb{N}$ in (1) and (2), and instead of it use a finite subset $B$, I think there are still "too many" functions and still there are no surjection, so I think either or "there is no surjection" is not enough to prove undecidability, or there are undecidable finite Languages. $\endgroup$
    – Hernan_eche
    Commented May 22, 2012 at 15:21
  • $\begingroup$ You can hard-code any finite language into a Turing machine that accepts only that language. "Is it string 1? Is it string 2? ... Is it string $n$? Okay, I guess it's not in the language." $\endgroup$
    – JeffE
    Commented May 22, 2012 at 15:30
  • 3
    $\begingroup$ @Hernan_e: "I think there are still "too many" functions" -- no, there are not. You need infinite sets to have an uncountable base set, and then there is no reason why a finite set should be undecidable (and in fact, as shown in the other question, they all are decidable). $\endgroup$
    – Raphael
    Commented May 22, 2012 at 16:01
  • $\begingroup$ @Raphael Perhaps I am mixing meanings of Undecidable Language with Undecidable Problems, I still don't find here an answer for my question. If you change (1) to a finite set $P$ of decision functions(not all posible functions) so $|P|=K$, some will define a decidable Language/inputs (indicator function==1), but perhaps some will not. We know that the powerset of P is bigger than K, then some of the possible indicator function will correspond to P but most won't!, just because 2^K possible languages is bigger than K possible problems, then there will be undecidable problems. $\endgroup$
    – Hernan_eche
    Commented May 22, 2012 at 19:30
  • 1
    $\begingroup$ @Hernan_e: I think what you say (about finite sets of functions) is true; I have a hard time understanding what you say. However, it is completely unrelated to the quote you say you have a problem with. Its (most likely) intended meaning is outlined in my answer. $\endgroup$
    – Raphael
    Commented May 22, 2012 at 19:36

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.