patternMinor
Why don't prefix-free Turing machines suffer from complexity dips?
Viewed 0 times
fromwhyfreesufferdipsmachinesprefixturingcomplexitydon
Problem
It's claimed in several texts on algorithmic complexity that prefix-free Turing machines are better for understanding randomness, at least in infinite sequences. In Nies' Computability and Randomness, the reason is given by theorems 2.2.1 and 2.2.2 on p. 83. I'll focus on the former, which states that for some plain (not prefix-free) machine there is a constant $c$ such that for each natural number $d$ and string $w$ of length $\geq 2^{d+1}+d$, there is a prefix $x$ of $w$ such that the plain complexity $C(x) \leq |x|-d+c$. (Here $|x|$ is the length of $x$.)
That is, if complexity is defined in terms of Turing machines that accept arbitrary strings as inputs, any sufficiently long string, no matter how complex, can have initial substrings with more or less arbitrary "dips" in complexity. The proof of the theorem uses a machine that uses the length of an input string to construct its output. This is apparently an important point (see below).
My question: Why can't a prefix-free machine do this, too? Why doesn't prefix-free complexity also allow dips in complexity of initial substrings? I have not yet found an explanation of this point that I understand in the algorithmic complexity textbooks by Nies, Downey and Hirschfeldt (see below), Li and Vitanyi (although it may be there somewhere), or Calude (Computability and Randomness). I think that Nies and D&H just think it's obvious, but I don't see why.
Some prefix machines: Downey and Hirschfeldt's Algorithmic Randomness and Complexity, p. 122, refers to a similar theorem proved earlier in the book, and remarks that a prefix-free machine can be thought of as one that reads an input until its finished, without moving in the opposite direction on the tape, and without any test for a termination-of-input character or pattern. The text says that "this highlights how using prefix-free machines circumvents the use of the length of a string to gain more information than is present in the bits of a string." I gu
That is, if complexity is defined in terms of Turing machines that accept arbitrary strings as inputs, any sufficiently long string, no matter how complex, can have initial substrings with more or less arbitrary "dips" in complexity. The proof of the theorem uses a machine that uses the length of an input string to construct its output. This is apparently an important point (see below).
My question: Why can't a prefix-free machine do this, too? Why doesn't prefix-free complexity also allow dips in complexity of initial substrings? I have not yet found an explanation of this point that I understand in the algorithmic complexity textbooks by Nies, Downey and Hirschfeldt (see below), Li and Vitanyi (although it may be there somewhere), or Calude (Computability and Randomness). I think that Nies and D&H just think it's obvious, but I don't see why.
Some prefix machines: Downey and Hirschfeldt's Algorithmic Randomness and Complexity, p. 122, refers to a similar theorem proved earlier in the book, and remarks that a prefix-free machine can be thought of as one that reads an input until its finished, without moving in the opposite direction on the tape, and without any test for a termination-of-input character or pattern. The text says that "this highlights how using prefix-free machines circumvents the use of the length of a string to gain more information than is present in the bits of a string." I gu
Solution
Answering the titular question, the proof of the proposition breaks down for prefix-free encodings, since $\sigma$ doesn't necessarily belong to the prefix-free code.
There are other ways of seeing that prefix-free programs are more well-behaved than plain programs. Suppose that we want to concatenate the output of two programs $P,Q$. With prefix-free programs, we can take a universal program that runs two input programs and concatenates their outputs, for a total length of $|P| + |Q| + O(1)$. With plain programs, this is impossible, since we need to separate the two programs $P,Q$ somehow, say by encoding them as $\mathit{len}(P)PQ$, where $\mathit{len}(P)$ is encoded using a self-terminating encoding. Thus we have to lose an additive term of $O(\log \min(|P|,|Q|))$.
There are other ways of seeing that prefix-free programs are more well-behaved than plain programs. Suppose that we want to concatenate the output of two programs $P,Q$. With prefix-free programs, we can take a universal program that runs two input programs and concatenates their outputs, for a total length of $|P| + |Q| + O(1)$. With plain programs, this is impossible, since we need to separate the two programs $P,Q$ somehow, say by encoding them as $\mathit{len}(P)PQ$, where $\mathit{len}(P)$ is encoded using a self-terminating encoding. Thus we have to lose an additive term of $O(\log \min(|P|,|Q|))$.
Context
StackExchange Computer Science Q#118695, answer score: 4
Revisions (0)
No revisions yet.