Principe et fonctionnement des automates cellulaires

Table des matières

Introduction…………………………………………………………………...2

1. Rappels Théoriques………………………………………………………..3

1.  Machine de Turing....................................................................................3

1. Définition……………………………………………………………….3
2. Fonctionnement de la machine de Turing……………………………....3

1.  Systèmes dynamiques…………………………………………………....4

1. Système dynamique à temps continu…………………………………...4
2. Système dynamique à temps discret……………………………………5

1. Les automates cellulaires…………………………………………………..6

1. Définition………………………………………………………………....6
2. Quelques exemples d’automates cellulaires………………………………6

1. Les automates cellulaires élémentaires…………………………………6
2. Le jeu de la vie………………………………………………………...13
3. Les autres types d’automates cellulaires………………………………16

Conclusion…………………………………………………………………….18

Références……………………………………………………………………..19

Introduction

Notre monde tel que nous le connaissons est d’une fantastique et remarquable complexité ; et pourtant à la base, il n’est fait que d’un nombre assez limité d’éléments chimiques, qui interagissent selon des lois relativement simples et bien connues. De fait l’apparition de la vie est sans aucun doute l’un des exemples les plus fascinants de cette question dans de nombreux domaines scientifiques.

Comment des objets simples interagissant selon des règles simples, peuvent-ils engendrer des comportements complexes ?

Grâce aux ordinateurs, on peut maintenant étudier cette question au moyen de programmes informatiques.

Pour ce faire nous pouvons y avoir recours aux automates cellulaires.

Les automates cellulaires sont à la fois un puissant modèle de calcul et un modèle de système dynamique discret introduits au début des années 50 par le mathématicien américain John Von Neumann qui s’intéressait alors à l’autoreproduction des systèmes artificiels. Le modèle des automates cellulaires est remarquable par l’écart entre la simplicité de sa définition et la complexité que peuvent atteindre certains comportements macroscopiques. De ce fait, il constitue un des moyens standards dans l’étude des systèmes complexes.

1. Rappels Théoriques

1. Machine de Turing

1. Définition

Une machine de Turing est un modèle abstrait de fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire. Ce modèle a été imaginé par Alan Turing en 1936. Une machine de Turing comporte les éléments suivants :

• un ruban infini divisé en cases consécutives. Chaque case contient un symbole parmi un alphabet fini. L’alphabet contient un symbole spécial appelé « symbole blanc ». On considère que les cases non encore écrites du ruban contiennent le « symbole blanc » ;
• une tête de lecture/écriture qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban ;
• un registre d’état qui mémorise l’état courant de la machine de Turing. Le nombre d’états est fini et il existe toujours un état spécial qui est l’état initial de la machine avant son exécution ;
• une table d’actions qui indique à la machine le symbole à écrire, comment déplacer la tête de lecture, quel est le nouvel état en fonction du symbole lu sur le ruban et l’état courant de la machine.

1.1.2        Fonctionnement de la machine de Turing

Une machine de Turing est un septuplet (Q, Γ, Β, Ʃ, q0, δ, F) où :

• Q est un ensemble fini d’états ;
• Γ est l’alphabet des symboles ;
• Β ∈ Γ est le « symbole blanc » ;
• Ʃ est l’alphabet des symboles en entrée (Ʃ ⊆ Γ \ {Β}) ;
• q0 ∈ Q est l’état initial ;
• δ : Q × Γ → Q × Γ × {←, →} est la fonction de transition ;
• F ⊆ Q est l’ensemble des états terminaux.

Les flèches dans la définition de la fonction de transition δ représentent les deux déplacements possibles de la tête de lecture/écriture. Par exemple, pour une fonction de transition δ(q1, a) = δ(q2, b, ←) signifie que si la machine de Turing est dans l’état q1 et qu’elle lit le symbole a, alors elle écrit le symbole b à la place de a, va dans l’état q2, puis déplace sa tête de lecture vers la gauche.

À chaque étape de son calcul, la machine évolue en fonction de l’état dans lequel elle se trouve et du symbole inscrit dans la case du ruban où se trouve à ce moment sa tête de lecture. À l’instant initial, la machine se trouve dans l’état q0, et le mot inscrit sur son ruban est l’entrée du programme. La machine s’arrête lorsqu’elle rentre dans un état terminal. Le résultat est ainsi le mot inscrit sur le ruban.

1.2        Systèmes dynamiques

L’objectif de la théorie des systèmes dynamiques est de modéliser des processus qui évoluent dans le temps et d’étudier leur comportement. Cette étude doit permettre de prédire le comportement du système et de le réguler afin d’obtenir les résultats souhaités. Pour élaborer un tel modèle il faut tout d’abord définir quelles sont les valeurs qui évoluent dans le temps, les états du système. Ensuite, il faut trouver des équations mathématiques qui décrivent leur évolution. Généralement, ce sont des équations différentielles (si le temps est considéré comme continu) ou en différences finies (si le temps du modèle est discret). Les paramètres du modèle sont les coefficients de ces équations et les conditions initiales.

...