31
$\begingroup$

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?

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

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

$\endgroup$
12
  • 5
    $\begingroup$ 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. $\endgroup$ – Mark Bennet Sep 29 '12 at 20:15
  • $\begingroup$ 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.... $\endgroup$ – Cameron Buie Sep 29 '12 at 21:59
  • $\begingroup$ @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. ;-) $\endgroup$ – stefan Sep 30 '12 at 0:28
  • 2
    $\begingroup$ 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. $\endgroup$ – celtschk Sep 30 '12 at 11:59
  • 1
    $\begingroup$ @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 :-) $\endgroup$ – Asaf Karagila♦ Oct 27 '12 at 1:27
29
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ 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. $\endgroup$ – Cameron Buie Sep 29 '12 at 19:33
  • 2
    $\begingroup$ @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. $\endgroup$ – Tim Seguine Nov 2 '12 at 22:55
  • $\begingroup$ @Tim: What do you mean by "when viewed outside the model"? $\endgroup$ – Cameron Buie Nov 2 '12 at 23:56
  • $\begingroup$ @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. $\endgroup$ – Tim Seguine Nov 3 '12 at 0:45
  • 3
    $\begingroup$ @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. $\endgroup$ – Jason DeVito Apr 3 '13 at 2:26
14
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – celtschk Sep 30 '12 at 12:11
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ However some of those programs will be ill-formed. Section 2.14.2 (Integer literals) paragraph 3 says that a program is ill-formed if the integer literal cannot be represented by any of the allowed types. And the types are required to have bounded range - which means there's an $N$ such that $P_n$ is ill-formed if $n>N$. $\endgroup$ – skyking Feb 1 '16 at 13:28
  • $\begingroup$ @skyking: Good point, perhaps { /* n times */ 1; 1; ... 1; 1; } instead? $\endgroup$ – copper.hat Feb 2 '16 at 18:39
1
$\begingroup$

The C++ differs from C in that part as it doesn't define limits of what the compliation or execution environment is required to handle. Consequently there are valid C++ programs that cannot be compiled by any implementation. Say you for example in your main nests $2^{2^{64}}$ curly brackets, the standard allows for this but there is no computer available that can count them, less store the source.

As pointed out in other comments. The set of finite strings with a finite non-empty alphabet is a countable (infinite) set. Some strings composed of the ASCII alphabet are valid C++ programs. So the programs are countable.

To see that they are infinite one could use the construct suggested above. Take a trivial program where main just returns 0. You can write the return statement as return followed by $N$ opening parentheses, a zero, followed by $N$ closing parentheses and followed by a semicolon (where $N$ is any natural number).

The C standard on the other hand puts limits on what the compiler is required to handle - here we end up with (probably) finitely many valid C programs that any compiler is required to handle.

$\endgroup$
0
$\begingroup$

The set of programs is countable: Set of all finite strings ( A subset such as set of all valid programs will be countable as well)

The set of all valid programs is not finite: If it is simply add a blank remark at the end of the largest program in the set....so the set of all valid programs has no largest program hence infinite.

Alternatively Since C++ is a Turing complete language and the total no of different Turing computable integer sequences are infinite the total number of valid programs can not be finite.

$\endgroup$
4
  • $\begingroup$ Concatenation of two valid programs need not result in a valid program. $\endgroup$ – skyking Feb 1 '16 at 13:31
  • $\begingroup$ Ok if not concatenation we can have an operation which takes two valid programs puts them in different scopes and generates a third program. Or just add a blank remark to the largest program. $\endgroup$ – ARi Feb 1 '16 at 13:39
  • $\begingroup$ While there are transformations that take two valid programs and glues them together to one valid programs these are not trivial to construct. You would for example have to handle complications brought by by the preprocessor, explicit scoping and possibly other problematic constructs. Just adding blank comments to a program on the other hand is a trivial way to create a new, longer progam. $\endgroup$ – skyking Feb 1 '16 at 13:56
  • $\begingroup$ @skyking I completely agree. The trivial method though serves the purpose. $\endgroup$ – ARi Feb 1 '16 at 14:40

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.