3 ms·
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 len
by Someone 15y ago
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.