Editing Kolmogorov complexity (section)

=== Prefix-free Kolmogorov complexity ''K'' ===
A prefix-free code is a subset of <math>2^*</math> such that given any two different words <math>x, y</math> in the set, neither is a prefix of the other. The benefit of a prefix-free code is that we can build a machine that reads words from the code forward in one direction, and as soon as it reads the last symbol of the word, it ''knows'' that the word is finished, and does not need to backtrack or a termination symbol.

Define a '''prefix-free Turing machine''' to be a Turing machine that comes with a prefix-free code, such that the Turing machine can read any string from the code in one direction, and stop reading as soon as it reads the last symbol. Afterwards, it may compute on a work tape and write to a write tape, but it cannot move its read-head anymore.

This gives us the following formal way to describe ''K''.<ref name=":0">{{Cite journal |last=Hutter |first=Marcus |author-link=Marcus Hutter |date=2007-03-06 |title=Algorithmic information theory |journal=Scholarpedia |language=en |volume=2 |issue=3 |pages=2519 |doi=10.4249/scholarpedia.2519 |doi-access=free |bibcode=2007SchpJ...2.2519H |issn=1941-6016|hdl=1885/15015 |hdl-access=free }}</ref>

* Fix a prefix-free universal Turing machine, with three tapes: a read tape infinite in one direction, a work tape infinite in two directions, and a write tape infinite in one direction.
* The machine can read from the read tape in one direction only (no backtracking), and write to the write tape in one direction only. It can read and write the work tape in both directions.
* The work tape and write tape start with all zeros. The read tape starts with an input prefix code, followed by all zeros.
* Let <math>S</math> be the prefix-free code on <math>2^*</math>, used by the universal Turing machine.

Note that some universal Turing machines may not be programmable with prefix codes. We must pick only a prefix-free universal Turing machine.

The prefix-free complexity of a string <math>x</math> is the shortest prefix code that makes the machine output <math>x</math>:<math display="block">K(x) := \min\{|c| : c \in S, U(c) = x\}</math>