How Many C Programs Are There?
blog.regehr.org
blog.regehr.org
There's a good reading that approaches a related subject, but isn't specific to C programs: http://www.scottaaronson.com/writings/bignumbers.html
In short, `busy beaver number' -- number of steps that a halting Turing machine with dictionary of size N can have -- grows pretty fast with N; faster than Ackermann function anyway.
Also, supposedly a katamari is the only thing which outgrows the busy beaver sequence ;) http://www.xamuel.com/katamari-damacy-growth/
Alas, it grows faster than any computable function.
I would rather try to evaluate the size of the abstract syntax tree. I think this is more relevant since int main(){int a;} is obviously similar to int main(){int b;}
> How many non-alpha-equivalent C programs are there?
and then goes further:
> How many functionally inequivalent C programs are there?
The "this" you're refering to is itself refering to this last question.
Surely this is undecidable?
Definitely. I can give a lower bound right off the top of my head: twelve. There are at least twelve functionally distinct C programs.
You probably want your bound to be a function of the length of the program. Because for programs of length 1, there are not 12 distinct C programs.
As to the number of a given length: if, for every possible output, we pick the shortest program producing it as a representative (utterly reasonable, as we know all programs to be optimal :-)), one should study how to sort outputs by their Kolmogorov complexity.