“Suppose an advanced agent with a goal like, e.g., producing smiles or making paperclips.”
Typo? Does not seem to be a complete sentence. Maybe “Suppose you have an...”
Kaya Fallenstein
Karma: 0
“Similarly, if you start with a 10 kilobyte text file, and 7zip compresses it down to 2 kilobytes, no amount of time spent trying to further compress the file using other compression programs will ever get that file down to 1 byte.” (Emphasis added.)
This claim seems too strong. Do you mean that an arbitrary compression algorithm is unlikely to compress the file to one byte?
Taking what’s written at face value, if I assume that every compression I apply monotonically decreases the size of the file, then I need only find a large enough sequence of compressions and compose them to compress my file to one byte. This is of course silly, since the composition is just a huge highly specialized compression program optimized for this instance, but I can spend enough time to make it happen.
tl;dr: I did some reading on related topics, and it turns out that (1) may be sufficient to define logarithms if we take as an axiom that every set is Lebesgue measurable (which is incompatible with the axiom of choice). Otherwise, we need to add an additional condition to (1).
(1) states that . Given a function satisfying this condition, we can generate an additional function satisfying this condition by composing with a function , where :
, as defined, is a solution to Cauchy’s functional equation. The family of functions given by for some constant is always a solution, giving the usual logarithm family. The existence of other solutions is independent of ZF. When they do exist they are always pathological and generate non-Lebesgue measurable sets (for more, see this stackexchange link).
We can prove the existence of such solutions in ZFC by noting that the solutions of the Cauchy functional equation are exactly the homomorphisms from the additive group of to itself. The real numbers form an infinite dimensional vector space over the field . Linear transformations from the vector space to itself translate into homomorphisms from the group to itself. Since the axiom of choice implies that any vector space has a basis, we can, for example, find a non-trivial linear transformation by swapping two basis vectors. This in turn induces a homomorphism from the group to itself. (The Wikipedia page gives the general form of a solution to this functional, which turn out to be all the linear transformations on the vector space.)
(I’m not saying that this article should discuss axiomatizations of set theory, but it doesn’t seem good to make statements that are only true if you assume, e.g., an unusual alternative to the axiom of choice.)
Wikipedia proves that the pathological solutions must all be dense in , so to exclude them, we can adopt any number of conditions. Wikipedia points at ” is continuous”, ” is monotonic on any interval”, and ” is bounded on any interval”. Continuity seems to be most intuitive; once we have defined the value of the function on the rationals (which we can do with basically the arguments already on this page), the rest of its values are determined.
The proof of (5) only goes through for .
You can prove a version of (8) from (5), namely, for , but this doesn’t pin down completely, unless you include a continuity condition.
(8) doesn’t follow from (5). The assumption in (5) was than ranged over naturals, not reals. In fact, (1) only implies (8) if you also require the function to be continuous.
(1) essentially says is a homomorphism from to . To generate a function satisfying (1) but not (8), we need only compose (choose a base) with an automorphism in the additive group and show that the composition is not a multiple of a logarithm. We can get such an automorphism by considering as an infinite dimensional vector space over the rationals and, for example, swapping two dimensions.
I only assumed the sequence was monotonic.
The second comment is fair. I think when I first read this, I ignored the bit about 7zip and understood the sentence as claiming “no Turing machine takes an input smaller than one byte and prints out a 10kb file”.