\( \newcommand{\llbracket}{[\![} \newcommand{\rrbracket}{]\!]} \renewcommand{\epsilon}{\varepsilon} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ACA}{\mathcal{A}} \newcommand{\ACC}{\mathcal{C}} \newcommand{\ACV}{\mathcal{V}} \newcommand{\ACQ}{\mathcal{Q}} \)

Historique (rappel)

Automates cellulaires

1940s. Systèmes dynamiques (2D puis 1D)
1960s. Algorithmes à base de signaux
1970s. Modèles de calcul

→ On peut donner une entrée, laisser l'automate calculer et obtenir une réponse

calcul de fonctions
reconnaissance de langages

Reconnaissance de langages (1D)

Alphabet fini \(\Sigma\)
Mots dans \(\Sigma^* = \bigcup_{n} \Sigma^n\)
Automate cellulaire \(\ACA=(1, \ACQ, \ACV, \delta)\)

\(\Sigma \subseteq \ACQ\quad\) (alphabet d'entrée)
\(◈ \in \ACQ\quad\) (état quiescent)
\(\ACQ_{\operatorname{acc}} \subseteq \ACQ\quad\) (états d'acceptation)

Entrée parallèle
Reconnaissance à l'origine
Complexité en temps et espace comme dans le cas Turing (\(f: \NN\rightarrow \NN\))

Reconnaissance de langages (2D)

Alphabet fini \(\Sigma\)
Mots dans \(\Sigma^{**} = \bigcup_{n, m} \Sigma^{(n, m)}\)
Automate cellulaire \(\ACA=(2, \ACQ, \ACV, \delta)\)

\(\Sigma \subseteq \ACQ\quad\) (alphabet d'entrée)
\(◈ \in \ACQ\quad\) (état quiescent)
\(\ACQ_{\operatorname{acc}} \subseteq \ACQ\quad\) (états d'acceptation)

Entrée parallèle
Reconnaissance à l'origine
Complexité en temps et espace comme dans le cas Turing (\(f: \NN^2\rightarrow \NN\))

Liens avec les modèles Turing

Sauf mention contraire, tous les AC 1D considérés fonctionnent sur le voisinage standard \(\{-1, 0, 1\}\)

✎ Proposition

Un langage est reconnu en espace \(s\) sur une machine de Turing ssi il est reconnu en espace \(s\) sur un AC 1D

✎ Proposition

Tout langage reconnu en temps \(t\) et espace \(s\) par un AC 1D est reconnu en temps \(t\times s\) par une MT à 1 ruban

✎ Proposition

Tout langage reconnu en temps \(t\) par une MT à 1 ruban est reconnu en temps \(t\) par un AC 1D

✎ Proposition

Tout langage reconnu en temps \(t\) par une MT à k rubans est reconnu en temps \(t\) par un AC 1D

Restriction de l'espace

✎ Proposition

Tout langage reconnu en temps \(t\) et espace \(s\) par un AC 1D est reconnu par un AC 1D en temps \(t\) et espace \(s\) sans utiliser les cellules \(c<0\)

Idée : on replie l'espace de travail

Rmq : On peut aussi replier l'espace à droite pour passer d'un espace \(n\mapsto kn\) à \(n\mapsto n\).

Accélération constante

✎ Proposition

Tout langage reconnu en temps \(n \mapsto n + k\) (\(k\in\NN\)) par un AC 1D est reconnu en temps \(n\mapsto n\) par un AC 1D

Chaque cellule essaie de deviner les états de ses \(k\) voisines en supposant initialement que ces états sont ◈
Les cellules \(c\geq n-1\) font des hypothèses correctes à \(t=0\)
Même si les hypothèses d'une cellule ne sont pas correctes, elle calcule correctement son état

Si \((c+1)\) est correcte au temps \(t\), \(c\) est correcte au temps \((t+1)\)
Au temps \((n-1)\) l'origine est correcte → elle peut anticiper \(k\) étapes de calcul

Accélération linéaire

✎ Proposition

Si un langage est reconnu en temps \(n\mapsto n + f(n)\) par un AC 1D, il est reconnu en temps \(n\mapsto n + \epsilon f(n)\) pour tout \(\epsilon > 0\) par un AC 1D

Il suffit de montrer le résultat pour \(k=2\)

On groupe les états par 2

On effectue deux transitions d’un coup dès que c’est possible

Au temps réel, le retard est rattrapé, et la configuration est « deux fois plus compacte » que dans l’automate de départ

Voisinages

Définition (puissances de voisinages)

Pour tout voisinage \(\ACV\) en dimension \(d\) \[\ACV^0 = \{0\}\] \[\ACV^{k+1} = \{x + y,\quad x\in\ACV^k, y\in\ACV\}\]

Voisinages complets

Définition (voisinages complets)

Un voisinage \(V\) en dimension \(d\) est dit complet si \[\forall c\in \ZZ^d, \exists k\in \NN, \quad c \in V^k\]

Proposition

Pour tous voisinages complets \(V_1\) et \(V_2\), il existe \(k\in\NN\) tel que tout langage reconnu par un AC sur \(V_1\) en temps \(t\) est reconnu par un AC sur \(V_2\) en temps \(kt\)

Temps réel

Définition (Temps réel)

Étant donné un voisinage \(\ACV\) en dimension \(d\), on définit le temps réel \[\TR_\ACV(n1, \ldots, n_d) = \min \{t\in \NN, \quad \llbracket 0, n_1-1\rrbracket \times \ldots \times \llbracket 0, n_d-1\rrbracket \subseteq \ACV^t\}\]

Le temps réel est le temps minimal à partir duquel l'état de l'origine dépend (potentiellement) de toutes les lettres du mot en entrée

Exemples

Voisinage standard \(\{-1, 0, 1\}\)

→ \(\TR(n) = n - 1\)
Voisinage de Moore \(\{(x, y), \max(|x|, |y|) \leq 1\}\)

→ \(\TR(n, m) = \max(n, m) - 1\)
Voisinage de von Neumann \(\{(x, y), |x| + |y| \leq 1\}\)

→ \(\TR(n, m) = n + m - 1\)

Temps réel et temps linéaire

Question ouverte

La classe des langages reconnus en temps réel par un AC 1D est-elle égale à la classe des langages reconnus en temps linéaire ?

On ne sait même pas si le temps réel est égal à l'espace linéaire
Tout langage reconnu en temps linéaire est reconnu en temps \((1+\epsilon)\TR\) pour tout \(\epsilon\)
Le temps réel et le temps linéaire peuvent être restreints à un espace \(n\mapsto n\)
En dimension quelconque les voisinages complets sont équivalents pour le temps linéaire
En dimension 1 les voisinages complets sont équivalents pour le temps réel
En dimension 2 la question est ouverte sur le voisinage de von Neumann
Sur le voisinage de Moore, on sait que le temps réel est strictement plus faible que le temps linéaire (V. Terrier)