2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Yes read How is the set of all programs countable? $\endgroup$ – Grijesh Chauhan Oct 3 '13 at 14:57
  • 6
    $\begingroup$ 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. $\endgroup$ – Patrick87 Oct 3 '13 at 20:42
  • $\begingroup$ 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. $\endgroup$ – scaaahu Oct 4 '13 at 7:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Gilles 'SO- stop being evil' Oct 4 '13 at 8:02
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ More generally, any language that consists only of finite strings is countable (either finite, or infinite-countable). $\endgroup$ – Gilles 'SO- stop being evil' Oct 4 '13 at 11:51
  • $\begingroup$ 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$. $\endgroup$ – Gilles 'SO- stop being evil' Oct 4 '13 at 12:29
  • $\begingroup$ @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. $\endgroup$ – Patrick87 Oct 4 '13 at 16:18
  • 1
    $\begingroup$ @Patrick87 Simpler to have a bunch of empty lines. $\endgroup$ – Gilles 'SO- stop being evil' Oct 4 '13 at 16:35
0
$\begingroup$

Your compiler effectively solves the word problem for C along the way. Therefore, the language of all C programs is decidable. This directly implies that it is countable.

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.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ My point is that it's roundabout because you don't even need to involve decidability. It's a subset of a countable language (the language of all finite strings). $\endgroup$ – Gilles 'SO- stop being evil' Oct 4 '13 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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