Quote:
Sternwallow wrote
Quote:
whoneedscience wrote
Quote:
Sternwallow wrote
The complexity of the output of a function is not, in principle, related to that of the function code or the code plus its execution.
Obviously, a long program whose output is only the value zero, is much more complex than its output. By the same reason, the program can be much less complex than its output.
|
If a function always outputs a constant, it reduces to a much simpler function. I would argue that the effective complexity should be considered from this reduced form, not from the needless computations that happen to be involved.
|
Computability issues suggest that it is not always possible to identify, by inspection, what code is needless. A function that returns "1" if a given string of digits appears in a contiguous section of the decimal expansion of Pi is not necessarily possible to simplify to one that ignores its input and returns "1" always.
|
I'm not sure where you're going there. I'm just talking about mathematically reducing a function.
If you had a function that performed a million multiply and the same number of divide operations to always output the exact same thing as the input, then its effective complexity is independent of those operations; it's just a unity gain, or effectively no operation at all.