Timeline for Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| May 22, 2012 at 19:37 | comment | added | Raphael | @Hernan_e: Note that if you can certainly select a finite sets of functions that include undecidable ones (e.g. the singleton set that contains only the halting function). But as I say, the quote does not relate to this at all. | |
| May 22, 2012 at 19:36 | comment | added | Raphael | @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. | |
| May 22, 2012 at 19:30 | comment | added | Hernan_eche | @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. | |
| May 22, 2012 at 16:24 | history | edited | Raphael | CC BY-SA 3.0 |
added 388 characters in body
|
| May 22, 2012 at 16:01 | comment | added | Raphael | @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). | |
| May 22, 2012 at 15:30 | comment | added | JeffE | 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." | |
| May 22, 2012 at 15:21 | comment | added | Hernan_eche | 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. | |
| May 22, 2012 at 14:44 | history | answered | Raphael | CC BY-SA 3.0 |