My PhD (French thèse de doctorat) was received on the 9th of October, 2000, at École normale supérieure de Lyon. The topic of the PhD was the "notion of prefix in Kolmogorov complexity and computational models", under the direction of Jacques Mazoyer and Bruno Durand.
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.