The prefix notion in Kolmogorov complexity and computational models
Kolmogorov complexity theory gives a definition of randomness for words on a finite alphabet. The notions involved led to the description of a subclass of computable machines: the prefix computable machines, whose domain is a prefix code (no word in the domain is prefix of another one).
Beyond the matter of
defining randomness for infinite words, this subclass has remarkable
properties regarding computability theory. Three different
definitions are given and compared. The case of comma free codes is
also examined, but it doesn't yield anymore an additively optimal
machine.
The notion of prefix also interacts with the
computational models. An examination of machines with no blank
characters or of finite models with an infinite calculus space (such
as the Turing machine, which uses an infinite tape) reveals a strong
influence of the prefix notion on computational processes.
lire la suite