How Many C Programs Are There?

There'd be a whole lot of programs.<p>There's a good reading that approaches a related subject, but isn't specific to <i>C</i> programs: <a href="http://www.scottaaronson.com/writings/bignumbers.html" rel="nofollow">http://www.scottaaronson.com/writings/bignumbers.html</a><p>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.<p>Also, supposedly <i>a katamari is the only thing which outgrows the busy beaver sequence ;)</i> <a href="http://www.xamuel.com/katamari-damacy-growth/" rel="nofollow">http://www.xamuel.com/katamari-damacy-growth/</a>

&#62; <i>Anyway, I’d be interested to hear people’s thoughts on this</i><p>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;}

I think it would make more sense to start by looking at research done on grammars. For instance:<p><a href="http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf" rel="nofollow">http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf</a>

<i>How many functionally inequivalent C programs are there?</i><p>Surely this is undecidable?

If you have printf, then "printf("long string")" where the string might be modified should give a good bound, say Omega(200^S). If you don't have it, what is the program allowed to do? Only return from main, without checking arguments? Then you have as many extensionally distinct programs as integers.