patternMinor
Number of possible programs in a language
Viewed 0 times
possiblenumberprogramslanguage
Problem
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#58028, answer score: 6
Revisions (0)
No revisions yet.