# Definition of a prefix-free Turing machine

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 ?

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