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

Question

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?

Answer 1

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. ;)

Answer 2

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.)

Answer 3

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.

Answer 4

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).

Answer 5

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.