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 ?

  • 2
    $\begingroup$ The question might be more suitable for Computer Science. $\endgroup$ – Kaveh Jun 3 '12 at 18:14
  • 1
    $\begingroup$ (the text doesn't say they are the same thing, it says it is usual to consider and that means they are essentially the same thing, i.e. they can be converted to each other easily.) $\endgroup$ – Kaveh Jun 3 '12 at 18:57

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.

| cite | improve this answer | |
  • $\begingroup$ Prefix machines never run out of bits ... the tape is assumed to be infinite. $\endgroup$ – Peter Shor Dec 19 '19 at 12:08

[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.)

| cite | improve this answer | |
  • $\begingroup$ I think the answer is now confusing because of the conflicting edits coexisting next to each other. In my opinion, it would be better to edit the answer to reflect your latest understanding. If anyone wants to see the history of your answer, they can click on the appropriate link. $\endgroup$ – Sasho Nikolov Dec 15 '19 at 19:11
  • $\begingroup$ OK, thanks @SashoNikolov. I will edit it as soon as I can. $\endgroup$ – Mars Dec 15 '19 at 21:53
  • $\begingroup$ @SashoNikolov thanks again for pushing me to clarify. I did some further reading, and now have removed my previous addition, which I think was incorrect, adding additional material about Li & Vitanyi to support my claims. $\endgroup$ – Mars Dec 18 '19 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.