  The plain Kolmogorov complexity measure is intuitively appealing. Yet the bewildering variety of permitted \(f\)-descriptions includes many unmanageable encodings. In particular, for a given decompression algorithm \(f\), there are \(f\)-descriptions \(\gamma\) and \(\delta\) such that \(\delta = \gamma\unicode{x2040}\tau\), for some string \(\tau\). This is an inefficient encoding, because if \(\gamma\) can occur both as a code itself, and as the initial part of another code, then an algorithm cannot decode its input string ‘on the fly’ as soon as it detects a comprehensible input, but must wait until it has scanned and processed the entire input before beginning to decode it. An efficient coding, such that no acceptable input is an initial substring of another acceptable input, is called prefix-free (because no member is a prefix of any other member). A good example of an encoding like this is the encoding of telephone numbers: the telephone exchange can, on input of a string of digits that it recognises, immediately connect you; once an acceptable code from a prefix-free set has been input, no other acceptable code can follow it.