Tag - computation model - Jean-Christophe Dubacq

Participation à JAC 2008

Friday 25 April 2008

À l’occasion du départ à la retraite de mon directeur de thèse Jacques Mazoyer a été organisée une conférence très sérieuse sur les thématiques qui lui sont chères, liées en particulier aux automates cellulaires. De nombreux intervenants extérieurs étaient là (venant de France bien sûr, mais aussi de Finlande, de Russie, d’Italie, du Maroc et du Chili).

Je n’ai mis dans cet article que les photographies de la conférence proprement dites ainsi qu’une analyse personnelle de ce que j’ai appris sur le domaine des automates cellulaires en 2008. Les autres photos que j’ai faites sont sur ma page personnelle. L’article détaillé est sur une autre page.

The prefix notion in Kolmogorov complexity and computational models

Tuesday 8 January 2008

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.

Introduction to the theory of algorithmic information

Sunday 6 January 2008

We explain the basics of the theory of the Kolmogorov complexity, also known as algorithmic information theory, and underline the main differences between the Kolmogorov complexity and Kolmogorov prefix complexity. Then, we introduce the definition of randomness for either finite or infinite words according to Per Martin-Löf and show that it is equivalent to the notion of uncompressibility defined via Kolmogorov complexity.

How to simulate Turing Machines by invertible cellular automata

Saturday 5 January 2008

Abstract of the article

The issue of testing invertibility of cellular automata has been often discussed. The computation universality of cellular automata has long been positively resolved, and by showing that any cellular automaton could be simulated by an invertible one having a superior dimension, Toffoli proved that invertible cellular automaton of dimension d ≥2 were computation-universal. Kenichi Morita proved that any invertible Turing Machine could be simulated by a one-dimensional invertible cellular automaton, which proved computation-universality of invertible cellular automata. This article shows how to simulate any Turing Machine by an invertible cellular automaton with no loss of time and gives, as a corollary, an easier proof of this result.

Internship reports

Thursday 3 January 2008

While studying at École normale supérieure de Lyon, I did two internships in labs in my undergraduate years (one in 1993, one in 1994), the first one in the LIPlab and the second in the IIT Madras (when Chennai / சென்னை was still Madras).

Jean-Christophe Dubacq