[Solved]: Are there more partially recursive functions than and recursive functions?

Problem Detail: 

Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ?

Asked By : chgsilva

Answered By : lPlant

No they have the same cardinality. They have the cardinality $\aleph_0$. Both sets are infinite in size so we have to compare them based on their level of infiniteness, since as we know there are infinite levels of infinity. Both sets are countably infinite so we say they have the same cardinality.

To expand on this and show why this is the case:

The set of partially recursive functions are infinite by design. Also they are computable, so by the Church-Turing thesis they are solvable by a Turing machine. Since there are only countably infinite Turing machines there can only be countably infinite partial recursive functions.

The same argument can be used on the set of recursive functions.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30205

3.2K people like this

 Download Related Notes/Documents