Hacker News Reader

I interpret 'functionally inequivalent' as 'produce different outputs'. With that, it is easy: there are aleph-0 such 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.

Yeah, proving extensional equality in general is undecidable. Maybe the author is thinking that the constrained input size matters?

He is looking for upper bounds.

Of course. But we ought to be able to establish some kind of bounds on the number.

> some kind of bounds

Definitely. I can give a lower bound right off the top of my head: twelve. There are at least twelve functionally distinct C programs.

> For every complex problem there is an answer that is clear, simple, and wrong.

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.

Zero is a good lower bound for all programs. Or minus one.

More than none. Less than all of them. :)