Is the number of possible programs usually finite or infinite? I'm playing with the idea of generating all possible programs for a language - is that even a finite number or must we be more specific, finite RAM etc?
$\begingroup$
$\endgroup$
asked May 29, 2016 at 18:28
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
6
When considering such questions we usually disregard limitations of real computers and think about a programming language theoretically.
A general-purpose programming language (any language used in practice falls into this category) has infinitely many programs. Furthermore, all programs can be generated systematically. Implementing a program which generates all programs may be a useful learning experience, but has little actual value. The number of all programs of length $n$ is exponential in $n$ and so is unfeasable, except for fairly small values of $n$.
answered May 29, 2016 at 19:11
-
1$\begingroup$ Besides the number of programs being impractical, for the common languages it's also the case that no interesting question about programs can be answered anyway. $\endgroup$ Commented May 29, 2016 at 22:19
-
$\begingroup$ Did you mean "can't be answered"? Well, extensional interesting questions can't. $\endgroup$ Commented May 30, 2016 at 5:56
-
$\begingroup$ I think I said what I meant (the negation comes earlier, on "interesting question"), though as you rightly point out I left many of the subtle (but fascinating!) technical details out of my description. $\endgroup$ Commented May 30, 2016 at 6:23
-
1$\begingroup$ Oops, never mind. I had a temporary lapse of English and parsed your negations in Slovene (in which negations are additive instead of multiplicative so you have to put them everywhere...) $\endgroup$ Commented May 30, 2016 at 16:34
-
$\begingroup$ I strongly disagree with your statement that generating all programs of a given size has little value: see my answer below. Also, besides the discovery of bijections, in my experience enumerating programs of small size can be quite useful in finding counterexamples to conjectures about a programming language. $\endgroup$ Commented May 30, 2016 at 17:46
$\begingroup$
$\endgroup$
The number of programs of any given length is finite. You can get an upper bound to the number rather simply: if the program's source code is $n$ bits long, then there are at most $2^n$ programs of that length. The real number will be far, far less, because of the need for programs to be syntactically valid. But any number less than a finite number is still finite, so "The number of programs of any given length is finite" still holds.
The number of programs of all finite lengths is infinite. This is depressingly easy to prove. In C++, take the programs which (apart from decoration) say x=1, x=2, x=3,… (and so on for ever) and you have your infinite list of programs.
The number of programs of all finite lengths is countable rather than uncountable. To show this, stick one binary digit $1$ to the front of the bit-stream representation of a program, and treat the resulting bit stream as a base-2 integer, most significant bit first. No two programs can have the same integer representation, so there are at most as many programs as there are integers, so the number of programs is at most as large as the number of integers, and "the number of integers" is the definition of countability.
$\begingroup$
$\endgroup$
As the other answers have indicated, in most programming languages of interest the set of possible programs is infinite. That means that in order to do any interesting combinatorics, you need to consider the programming language as a family of finite sets of programs, indexed by some parameter (such as "length"). This is a quite general pattern in combinatorics, though, so not really a reason to worry. For example, there are infinitely many binary trees, but we can enumerate all the binary trees with a given number $n$ of internal nodes, which yields the sequence of Catalan numbers $C_n = \frac{1}{n+1}{2n\choose n}$.
If done with appropriate care, enumerating all of the programs of a given size can actually be very interesting! (I strongly disagree with Andrej's assessment that it is of little value.) For example, analogous to the case of the Catalan numbers (which count not just binary trees but also strings of well-balanced parentheses, noncrossing partitions, and a myriad of other families of objects), it can lead to the discovery of bijective correspondences between programs and other families of other objects, hence to new ways of thinking about a programming language.
In fact, this is exactly what has happened recently with the discovery of unexpected connections between different fragments of lambda calculus and different families of graphs embedded on surfaces. For example, the sequence $L_n$ counting the number of closed linear lambda terms of a given size $n$ is OEIS sequence A062980, which it turns out also counts rooted trivalent maps (3-regular graphs embedded on a compact oriented surface without boundary) by number of edges. Combinatorists already know all sorts of properties about this sequence — for instance, they can prove that asymptotically
$$L_n \sim \frac{3\cdot 6^n \cdot n!}{\pi}.$$
Moreover, this numerical coincidence can be explained constructively as a bijection between linear lambda terms (of size $n$) and rooted trivalent maps (with $n$ edges), see:
O. Bodini, D. Gardy, and A. Jacquot. Asymptotics and random sampling for BCI and BCK lambda terms. Theoretical Computer Science, 502:227–238, 2013. (pdf)
N. Zeilberger. Linear lambda terms as invariants of rooted trivalent maps. December 21, 2015. arXiv:1512.06751. (pdf)
The second paper also shows how to use this bijection to give a natural lambda calculus reformulation of the Four Color Theorem.
Since this is fairly recent work, the applications of these connections are still difficult to foresee, but I think it's safe to say that enumeration of programs can lead in quite unexpected directions!
