more DaveInTucson's comments

DaveInTucson · on Feb 21, 2012

How many functionally inequivalent C programs are there?

Surely this is undecidable?

Someone · on Feb 21, 2012

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.

evincarofautumn · on Feb 21, 2012

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

tetha · on Feb 21, 2012

He is looking for upper bounds.

monochromatic · on Feb 21, 2012

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

mistercow · on Feb 21, 2012

> 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 · on Feb 21, 2012

> 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 · on Feb 21, 2012

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

cheald · on Feb 21, 2012

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

DaveInTucson · on May 20, 2011

It's been a long time since I had my Theory of Computation class, but as I recall, the proof that there are computationally undecidable questions uses the same diagonalization technique[1] used to demonstrate that the real numbers are not countably infinite.

The same technique can be used to show there are still computationally undecidable questions if you have a Turing Machine with an Oracle.

This proof technique suggests not only are there undecidable questions, there are uncountably many of them. Even if you have an Oracle.

[1] c.f. http://en.wikipedia.org/wiki/Cantors_diagonal_argument

DaveInTucson · on April 26, 2011

why this does not work: [1,2,3].map({2:4}) (in JavaScript)?

It does (or, at least, it can) if you give Array.prototype.map a suitable value. Here's one possible implementation:

  Array.prototype.map = function(o) {
    var copy = this.slice(0); // copy semantics
    for (var i in o) copy[i] = o[i];
    return copy;
  }