2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Yes read How is the set of all programs countable? $\endgroup$ Oct 3, 2013 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, 2013 at 20:42
  • 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$ Oct 4, 2013 at 8:02

2 Answers 2

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.

$\endgroup$
5
  • 1
    $\begingroup$ More generally, any language that consists only of finite strings is countable (either finite, or infinite-countable). $\endgroup$ Oct 4, 2013 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$ Oct 4, 2013 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, 2013 at 16:18
  • 1
    $\begingroup$ @Patrick87 Simpler to have a bunch of empty lines. $\endgroup$ Oct 4, 2013 at 16:35
  • $\begingroup$ Why do you assume a C program should be of finite length? $\endgroup$
    – Anixx
    Jan 4, 2021 at 21:22
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.

$\endgroup$
1
  • 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$ Oct 4, 2013 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.