Definition of a prefix-free Turing machine

Question

A prefix-free function is one whose domain is prefix-free. Similarly, a prefix-free (Turing) machine is one whose domain is prefix-free. It is usual to consider such a machine as being self-demiliting, which means that it has a one-way read head that halts when the machine accepts the string described by the bits read so far. The point is that such a machine is forced to accept strings without knowing whether there are any more bits written on the input tape.

From Downey and Hirschfeldt, Algorithmic Randomness and Complexity, page 122.

I don't understand why such a device would ensure that the domain of the function is prefix-free. Take a word $\omega$ accepted by the machine. Then, as the next bits won't be read, $\omega \eta$ is also accepted. So $\omega$ and $\omega \eta$ are in the domain, which is not prefix-free.

Where am I wrong ?

Answer 1

If you were using a self-delimiting machine as described, you have to change your notion of what it means for the machine to accept a string. You want to say that the machine accepts a string $\omega$ if it halts in an accept state with the read head on the last symbol. The idea is to think of the computation as a loop: it first asks whether $\omega\upharpoonright 1$ is in the language, then whether $\omega \upharpoonright 2$ is, and so forth, and it halts if it finds a prefix of $\omega$ in the language or if it runs out of bits of $\omega$.

The point is that if the input tape contains an infinite juxtaposed sequence of nonempty words from the language, the prefix free machine can be used to parse out the individual words from the sequence. The definition of a prefix-free machine from the book is designed for this sort of application, not for the problem of deciding whether an individual word is in the language.

Answer 2

[Second major edit since first posting:]

This is a supplement to @CarlMummert's answer, with some slight disagreement or clarification. (He surely knows more than I do in this area, though, so I may have a misunderstanding.)

In the prefix-free machine that D&H describe, the internal structure of the machine is such that it will simply stop reading when it gets to the end of the prefix-free input. Whatever is beyond that point will never be read under any condition. Anything can be on that further part of the tape, and it will make no difference to the behavior of the machine.

One might look at it this way: What sense is there to saying that a sequence of values is "accepted" by the machine when they can never make any difference to the output?

(Or if we do start by thinking that the part of the tape beyond the prefix-free input is also "accepted", then since arbitrary extensions of the prefix-free input are accepted in this sense, we might as well factor them out of what counts as the accepted string, and say that only the prefix-free string is accepted.)

I don't think that prefix-free machines have any special connection to parsing distinct words. There is nothing in the description of prefix-free machines that suggests that they are supposed to advance beyond the end of a prefix-free input to look for a subsequent input. That's not how the concept of a Turing machine is typically used; Turing machines just map single inputs to single outputs (even if they code ntuples).

In another text in the same area as D&H's, Li & Vitanyi 2008 3d, p. 7 (section 1.2) explains that one can encode a pair of natural numbers $\langle x, y \rangle$ as a unique natural number $y + (x + y + 1)(x + y)/2$. In chapter 3, L&V describe prefix-free machines in several ways, specifying in a few places (pp. 200, 201, 209) that when a prefix-free machine reads a program string, all operations halt once the last element of the prefix-free string has been read, and the next element is never read. On page 202, L&V define a universal prefix machine $U$ whose argument three other arguments using the page 7 encoding (cf. p. 105). (On the other hand, later on the same page, L&V define the prefix complexity of a pair of strings using a machine $V$ that reads two prefix-free strings separately and then outputs an encoded version of a pair of outputs. That is like what I take Carl Mummert to describe, but as I interpret the text, $V$ is not a prefix-free machine. It's certainly not one that stops after it reads a complete prefix-free string.)

(I'm not sure whether the read-only forward-only behavior that D&H describe in the quoted passage is required for prefix-free machines. This is part of a question I asked in cs.SE.)