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 ?

  • 1
    $\begingroup$ The question might be more suitable for Computer Science. $\endgroup$ – Kaveh Jun 3 '12 at 18:14
  • $\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.


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.