Problem Detail: 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.
Asked By : Hernan_eche
Answered By : Kaveh
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1993 Ask a Question Download Related Notes/Documents
