Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have to prove that computable functions (by computable we mean recursive functions or functions calculated by a program with a register machine) are countable. Let $\mathcal{C}$ be the set of computable $\mathbb{N} \to \mathbb{N}$ functions

$|\mathcal{C}|\geq\omega$. Well, this is trivial because we can consider functions of the kind $n \mapsto (s\circ\cdots \circ s)(n)$ where $s$ is the successor function; these maps are trivially computable and there are $\omega$ of them.

$|\mathcal{C}|\leq\omega$. We know that (I will not go in deeper details, but it can be done!) starting from a natural $j$, we can find a program $p_j$ tha computes a recursive function. Note that there are several programs computing the same function. In turn, we can consider a computable function $f$ and, since there is an entire class of programs that calculate $f$, we can map $f$ tho the minumum program index $j$ of a program that computes $f$. So we have an injective function between $\mathcal{C}$ and $\mathbb{N}$. QED

Is thi proof correct?

share|cite|improve this question
Looks fine to me. – Brian M. Scott Jun 22 '12 at 17:16

I think the proof to show that that the set of computable function is countable is far more basic than what you have above.

All partial computable functions can be enumerated by natural numbers. This is essentially the existence of the universal Turing Machine. Hence there are only countably many partial computable functions. The total computable functions are just those partial computable functions that happen to be totally defined. Hence the total computable functions are a subset of the countable set of partial computable functions. Subset of countable sets are countable.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.