\( \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}} \)

Reconnaissance de langages

Cours M2 - MIT
Victor Poupet
\(\newcommand{\TR}{\operatorname{TR}}\)

Historique (rappel)

Automates cellulaires


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

Reconnaissance de langages (1D)


Reconnaissance de langages (2D)


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

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

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 ?