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.

A few words on my thesis

I passed the PhD examination successfully (this making me Dr Dubacq) in presence of my examiners: Serge Grigorieff (president of the comittee and reviewer of the report), Jean-Yves Marion (in stead of Adam Cichon, also reviewer), both of my PhD advisors, François Denis and Véronique Terrier.

The report expores first the basics of Kolmogorov complexity, the goes on defining several kinds of prefix (Turing) machines. The idea is to capture what is the computation when some constraints are laid on the input tapes, such as all the words belonging to a prefix code. One can distinguish the empty machines that reject anything not in the code, the full machines that accept anything that is a continuation of (begins with) a word of the code (and gives it the same value as if it was the word of the code). One can easily define mixed machines, that do either accept with the same value or reject continuations of words in the code, and double-prefix machines (where double-prefix codes are used, continuations on both sides).

The main result is that (most of) all computability theory theorems hold for these subclasses of machines, even an internal version of the s-m-n theorem (except for the double prefix machines). Moreover, those classes are shown to be distinct (I construct an example of an empty machine whose frontier can not be the frontier of a full machine, for some simple definition of frontier).

The last part uses these considerations to describe the computation as something that happens in an infinitely large space, not an arbitrary large one. This modelisation fits quite well to three parts, a computing engine that acts on an infinite medium and a couple of encoding/decoding functions that transport the inputs (resp. outputs) from the world of finite words to the infinite medium (resp. the converse). Some properties of this modelisation are explored, especially with respect to what can be inferred from the encoding function (it can encode oracles in the infinite part of the medium).

This last part was one of the driving force between this PhD, especially with respect to the difference between cellular automata and Turing machines. I had spotted that cellular automata could be (somehow) more powerful than Turing machines, given the right initial condition, and this always bothered me. I am a bit more clear about that now.

Citing this document

The document is in French.

@PhdThesis{dubacq00,
  author = 	 {Jean-Christophe Dubacq},
  title = 	 {Notion de pr\'{e}fixe dans la complexit\'{e} de Kolmogorov et les mod\`{e}les de calcul},
  school = 	 {\'Ecole normale sup\'erieure de Lyon},
  year = 	 {2000},
  type = 	 {Th\`ese de doctorat},
  month = 	 oct
}

Jean-Christophe Dubacq