Timeline for Is there an undecidable finite language of finite words?
Current License: CC BY-SA 3.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 24, 2012 at 13:02 | vote | accept | Hernan_eche | ||
| May 24, 2012 at 13:02 | history | edited | Hernan_eche | CC BY-SA 3.0 |
added 95 characters in body
|
| May 23, 2012 at 18:39 | comment | added | Hernan_eche | @Gilles you're right, and that's a source of misunderstanding in my question, I was trying to use the set and powerset cardinals to prove existence of undecidable language in an specific case, thanks | |
| May 23, 2012 at 18:29 | comment | added | Gilles 'SO- stop being evil' | @Hernan_e If you write “undecidable” with no qualification, it means undecidable by a Turing machine (i.e. for the usual notion of computation). If you are studying decidability in other computation models, there may or may not be a finite decidable language, depending on the model. | |
| May 23, 2012 at 18:18 | comment | added | Hernan_eche | @DavidLewis I still think it's not end of story, because I try to work with a finite model, and to see if there is a way to apply #set < #powerset to show there is a finite undecidable language, please read the comments on Ran G answer, thanks | |
| May 23, 2012 at 18:18 | comment | added | Hernan_eche | @Gilles I agree, for a Turing Machine, but if you do not allow an unbounded program size, then I think there are bigger restrictions | |
| May 23, 2012 at 18:02 | vote | accept | Hernan_eche | ||
| May 23, 2012 at 18:05 | |||||
| May 23, 2012 at 5:30 | answer | added | Ben | timeline score: 2 | |
| May 23, 2012 at 4:55 | answer | added | Ran G. | timeline score: 15 | |
| May 22, 2012 at 19:42 | comment | added | Gilles 'SO- stop being evil' | @Hernan_e To explain why “there is no surjection from $\mathbb{N}$ onto $\mathscr{P}(\mathbb{N})$, thus there must exist an undecidable language” doesn't extend to finite languages: the reason is that a decidable language has to be enumerable, that is, at most as big as $\mathbb{N}$. If $L$ is finite then $\mathscr{P}(L)$ is bigger but still finite and hence smaller than $\mathbb{N}$. | |
| May 22, 2012 at 17:38 | history | edited | Kaveh |
edited tags
|
|
| May 22, 2012 at 17:16 | history | tweeted | twitter.com/#!/StackCompSci/status/204984042817458176 | ||
| May 22, 2012 at 14:10 | comment | added | David Lewis | 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. | |
| May 22, 2012 at 14:07 | comment | added | Hernan_eche | @Raphael That's this question intention, but I could create a new one if that's a more clear rewording | |
| May 22, 2012 at 14:00 | comment | added | Raphael | 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. | |
| May 22, 2012 at 13:58 | comment | added | Hernan_eche | @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)$ | |
| May 22, 2012 at 13:51 | comment | added | Raphael | 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. | |
| May 22, 2012 at 13:50 | history | edited | Raphael | CC BY-SA 3.0 |
deleted 4 characters in body
|
| May 22, 2012 at 13:47 | answer | added | Raphael | timeline score: 8 | |
| May 22, 2012 at 13:42 | history | edited | Hernan_eche | CC BY-SA 3.0 |
deleted 37 characters in body
|
| May 22, 2012 at 13:36 | history | edited | Hernan_eche | CC BY-SA 3.0 |
deleted 37 characters in body
|
| May 22, 2012 at 13:31 | comment | added | Raphael | There seem to be (at least) three questions here. Please concentrate on one and edit out the others. | |
| May 22, 2012 at 13:26 | history | edited | Hernan_eche | CC BY-SA 3.0 |
edited title
|
| May 22, 2012 at 13:14 | answer | added | Sam Jones | timeline score: 10 | |
| May 22, 2012 at 13:11 | history | asked | Hernan_eche | CC BY-SA 3.0 |