# Is the set of all valid C programs countable?

Is the set of all syntactically valid C programs countable or uncountable?

• – Grijesh Chauhan Oct 3 '13 at 14:57
• The set of all finite strings is countable; every valid C program is a finite string; so the set of all valid C programs is countable. – Patrick87 Oct 3 '13 at 20:42
• You posted your answer immediately after you posted your question. I am not sure if this is allowed. To me, you're gaming the system to gain reputation. Thus, downvote. – scaaahu Oct 4 '13 at 7:32
• @scaaahu Answering one's own question is perfectly allowed, please see the help center (formerly FAQ). If you already known the answer when you post the question, then posting the answer immediately is appropriate. Please vote on posts based on the posts themselves, not based on external context: if you think this question is unclear or not useful, feel free do downvote it, but do not downvote based on the existence of an answer. – Gilles 'SO- stop being evil' Oct 4 '13 at 8:02

Infinite. Countable. Given a length $l$, and a finite number of characters, $c$, we know that each length has only finitely many possible valid c codes $c^L$. We can easily make a bijection from the natural numbers to the lengths, and at each length we add only finite number of other valid code, thus countable.
• By the way, you didn't prove that the number of C programs is infinite. This requires that $c^l$ is nonzero for infinitely many values of $l$. – Gilles 'SO- stop being evil' Oct 4 '13 at 12:29
• @Gilles True, but a simple addendum constructing some infinite subset of valid C programs would finish this off. Something like: int main(void) { int x = 1; [x = (x + 1) % 32;]* printf("%d\n", x); return 0; }, where the stuff in square brackets is repeated indefinitely, or something. – Patrick87 Oct 4 '13 at 16:18
For any decidable language, build your bijection with $\mathbb{N}$ like this: enumerate all strings according to a fixed order and without repetition. Check for each whether it is in the language using your decider. On input $n$, output the $n$-th string the decider accepts. For the other direction, just count the number of accepted strings until you reach the input string.