7 ms·
How many functionally inequivalent C programs are there? Surely this is undecidable?
by DaveInTucson 15y ago
How many functionally inequivalent C programs are there?
Surely this is undecidable?
- evincarofautumn 15y agoYeah, proving extensional equality in general is undecidable. Maybe the author is thinking that the constrained input size matters?
- tetha 15y agoHe is looking for upper bounds.
- monochromatic 15y agoOf course. But we ought to be able to establish some kind of bounds on the number.
- mistercow 15y ago> 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.
- monochromatic 15y ago> 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.
- loboman 15y agoZero is a good lower bound for all programs. Or minus one.
- cheald 15y agoMore than none. Less than all of them. :)
- Someone 15y agoI 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.