d‘une bande magnétique virtuellement infinie
sur cette bande peuvent être lus des caractères d‘un alphabet simplifié ({0,1} ou {a, b, c}...),
l'automate se dompose de transitions simples : dans un état E, en lisant le caractère x, il doit passer à un état F (qui n‘est pas forcément différent de E), écrire un caractère y et se déplacer soit vers la droite, soit vers la gauche.

On peut démontrer que tout programme peut se ramener à une machine de Turing.

Voici un exemple de machine de Turing (tiré de wikipedia)

Alphabet = {0,1}
Etats = {e1, e2, e3, e4, e5}

  Etat  Lu  → Etat' écrit sens
  e1    1           e2     0    R
  e1    0           arrêt
  e2    1           e2     1    R
  e2    0           e3     0    R
  e3    1           e3     1    R
  e3    0           e4     1    L
  e4    1           e4     1    L
  e4    0           e5     0    L
  e5    1           e5     1    L
  e5    0           e1     1    R

Quand la bande initiale est

00001100000

et que la tête de lecture est sur la case 5 (le 1 le plus à gauche), il ne reste plus qu'à faire tourner le programme pour voir ce qui se passe.

Écrire une machine de Turing qui vérifie que le mot est composé d‘autant de a que de b. Alphabet={a, b, c, x} où x est une lettre imposant l'arrêt de la bande.

Dernière mise à jour le 21/4/2025 21h00

Rajout d'un plan plus détaillé.

Informatique Fondamentale Computer Science 001

Spring 2025

Overview

Ch I) Logique et ensembles

I.A) Algèbre booléenne

I.A.1) Binaire

I.A.2) Expressions booléennes

I.A.3) Propriétés

I.A.4) Premier TD

I.B) Ensembles

Ch II) Relations et fonctions

Ch II.A) Relations

Ch II.B) Fonctions

Ch III) Récurence

Ch IV) Langages

Ch IV.A) Langages

Ch IV.B) Expressions régulières

Ch IV.C) Langages

Ch IV) Machines de Turing

Ch IV) Machines de Turing

Informatique Fondamentale
Computer Science 001