# Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite.

I don't understand why though. A programming language has open curly braces and corresponding closing ones. Wouldn't one need a stack to track the braces? Hence, how can one design a DFA that accepts valid C++ programs?

-
valid c++ $\subset \Sigma^*$ and $\Sigma^*$ (all strings of alphabet $\Sigma$) is countably infinite, –  ratchet freak Sep 29 '12 at 20:33

Well, a valid C++ program (or really any C++ program) will simply be a finite sequence composed of a finite collection of characters and a few other things (indentation, spaces, etc.). It is a general result that the set of all finite sequences of entries from a finite alphabet will be countably infinite. To show that there are countably infinitely many valid C++ programs, you need only show there is no finite upper bound on the length of valid C++ programs.

Addendum: Another approach (an alternative to showing there is no finite upper bound on length) is to actually explicitly define (in a theoretic sense) countably infinitely many valid C++ programs. For example, for a given positive integer, the program that simply prints said integer, then ends (as I mentioned in the comments below).

The following program template should do the trick:

 #include<iostream>
using namespace std;

int main ()
{
cout << "___________";
return 0;
}


That "____" part is the spot where you'd type in whatever positive integer you wanted the program to print out--whether that be $1$, or $23234$, or $1763598730987307865$, or whatever--instead of the underscores.

Now, obviously, no matter how fast you can type, there are integers big enough that you couldn't finish typing in your lifetime, so in practice, there are programs of this type that you could never finish. Even if such a program were handed to you, you'll certainly run into memory problems for sufficiently large integers (depending on the computer), but should still be valid programs. We can say that such programs all exist in a "theoretical" sense. That is, given sufficient memory and power to store and run it--necessarily a finite (though perhaps prohibitively large) amount--and given sufficient time to program and run it--necessarily a finite (though perhaps prohibitively long) amount--this program will do what it's supposed to do.

Please don't give me any grief about the heat death of the universe or anything like that. ;)

-
I think it is easy to show that the number of valid C++ programs is infinite - there are a number of quite trivial infinite families. The language argument shows that they are countable. How to create an algorithm to recognise a valid C++ program depends on the notion of validity. For example there could be some kind of potentially invalid branch which is provably never called. Is this a valid or invalid program (assuming the rest is OK)? Is the question whether the program can be compiled - in which case one test is to give it to a compiler and see what happens. –  Mark Bennet Sep 29 '12 at 20:15
Yeah, if I actually knew more about the language (specifically, validity of a program), I'd have suggested an algorithm. I suppose one could always just refer to the program that just prints a given positive integer, then ends. There are readily countably infinitely many of those, and moreover, they can't be bounded in length.... –  Cameron Buie Sep 29 '12 at 21:59
@CameronBuie just with printing a positive integers you're running into the simple problem of finite memory on every machine. So you can only represent a limited amount of numbers. But putting these crazy thoughts aside, your argument obviously still holds. ;-) –  stefan Sep 30 '12 at 0:28
C++ is not bound to a specific implementation. Every single implementation may (and will) have resource limits, that is, for any C++ implementation there will be a valid C++ program which cannot be handled by the given C++ implementation. So not being able to compile and/or execute a program on any given machine doesn't make it an invalid C++ program (nor the implementation of C++ a non-conforming implementation, as long as it documents its resource limits). Since C++ does not put any upper limit on the size of pointers, it also does not put a limit on the memory a C++ program can use. –  celtschk Sep 30 '12 at 11:59
@Spenser: Every C++ code is necessarily finite; and its content come from a finite alphabet. Therefore the fact that there is an infinite set of programs means that this set is countably infinite. @Cameron: I think you need a pretty big bignum library for this sort of code :-) –  Asaf Karagila Oct 27 '12 at 1:27
show 7 more comments

Countably infinite doesn't mean regular. The C++ grammar isn't regular. In fact, it isn't even context free. Yet, the set of all valid C++ programs is countably infinite. To see why, first notice that it's infinite. No matter what $n \in \mathbb{N}$ you pick, you can always write a C++ program that is longer than $n$. Next, let $S_n$ be the set of all C++ programs of length $n$. Each $S_n$ is finite. The set of all C++ programs (of all possible lengths) is a countable union of sets $S_n$:

$$S = \bigcup_{n=0}^\infty S_n$$

Since the countable union of countable (or finite) sets is at most countable, we conclude that the set of all valid C++ programs is countable.

-
There are models of ZF in which $\Bbb R$ is a countable union of countable sets, so a countable union of countable sets need not be countable. That's not relevant to the topic at hand, of course, but still true. –  Cameron Buie Sep 29 '12 at 19:33
@CameronBuie Your comment is slightly misleading, since the reals are countable when viewed outside of the model, but viewed inside the model they are uncountable. Basically the poster's statement is true even in a countable model of ZF when viewed from inside of that model, whereas the reals are not a countable union of countable sets when viewed from inside the model, regardless of the countability of the model. –  Tim Nov 2 '12 at 22:55
@Tim: What do you mean by "when viewed outside the model"? –  Cameron Buie Nov 2 '12 at 23:56
@CameronBuie Basically, I'm not sure if you understand Skolem's paradox properly. There are countable models of ZF. Using this model it is perfectly possible to proof the uncountability of the real numbers using cantor's diagonal argument. Thus, in the model, the reals are uncountable, even though the model itself is countable. You are confusing statements about the model with statements in the model. –  Tim Nov 3 '12 at 0:45
@Tim: I'm way late to this, but Cameron is correct. The fact that the countable union of countable sets is countable does use the axiom of choice. There are models of ZF (but not of ZFC!) where $\mathbb{R}$ is (internally) a countable union of countable sets. This has nothing to do with Skolem's paradox. –  Jason DeVito Apr 3 at 2:26
show 7 more comments

A C++ program is a finite sequence of characters in a specified finite alphabet. The set of all finite sequences of characters in that alphabet is countably infinite. The set of all valid C++ programs is a subset of the set of all finite sequences of characters in that alphabet. An infinite subset of a countably infinite set is countably infinite.

(It's infinite because there is no finite upper bound on the lengths of C++ programs.)

-

I propose the following:

1. Each natural number is a program (a file is nothing but a very large number).

2. Some of these programs are valid C++ programs.

If we show now, that for every valid C++ program n, there exists a program n + m that is a valid C++ program as well, the number of C++ programs is countable infinite.

1. Let n_0 be a classical hello world program.

2. for every n, there is a m that adds a trivial line to n ( cout<<"Hello!";)

3. Proofed.

-

As several posters already have pointed out, the set of valid c++ programs is countably infinite.

The OP's concern has some merit though. On an actual computer, the memory is finite, so a valid program is not just a certain finite string, but a finite string of bounded length, and thus the set of valid, parsable programs on a specific computer is finite (but extremely large).

-
While on any given computer the memory is finite, you still can just build a bigger computer. Also, there is nothing in the C++ standard demanding that a valid C++ program must at some instance of time be stored completely on the computer. –  celtschk Sep 30 '12 at 12:11

It is clear that since a C++ program is generated from a finite alphabet that the number of programs is at most countable.

To see that it is countable, consider the programs $P_n$ defined by

int main() { <n>; }


where '< n >' is replaced by the decimal representation of $n$.

It is easy to see that $n \mapsto P_n$ is injective.

Only two braces needed.

-