La définition formelle d’une machine de Turing connaît de légères variantes, mais il s’agit essentiellement d’un tuple (une liste ordonnée) comprenant

• les états Q
• l’état initial q₀ ∈ Q
• l’alphabet d’entrée Σ
• l’alphabet de ruban Γ, où Σ ⊆ Γ
• le symbole vide b ∈ Γ
• la fonction de transition δ, de type Q × Γ → Γ × {L, R} × Q

où Q, Σ et Γ sont des ensembles finis non vides. Certaines définitions exigent en outre que le symbole vide ne fasse pas partie de l’entrée (b ∉ Σ).

À titre d’exemple, voici une description formelle de la machine « incrémentation binaire » :

Q = { right, carry, done }
q₀ = right
Σ = { 1, 0 }
Γ = { 1, 0, ' ' }
b = ' '

δ(right, 1) = (1, R, right)
δ(right, 0) = (0, R, right)
δ(right, ' ') = (' ', L, carry)
δ(carry, 1) = (0, L, carry)
δ(carry, 0) = (1, L, done)
δ(carry, ' ') = (1, L, done)

Notez que, par souci de simplicité, le simulateur limite chaque symbole à un seul caractère. De plus, l’entrée n’est pas vérifiée par rapport à un alphabet d’entrée, ce qui évite d’avoir à définir les alphabets d’entrée et de ruban.

(Le comportement d’une machine de Turing peut également être décrit en termes mathématiques. Sans entrer dans les détails, cela consiste à définir comment une configuration de la machine - son état, le contenu du ruban et la position de la tête de lecture (la cellule courante) - mène à la configuration suivante, à partir de la fonction de transition. Pour commencer, le contenu du ruban peut être défini comme une fonction des entiers vers les symboles, la position de la tête étant un entier, et chaque déplacement {L, R} ajoutant respectivement -1 ou +1 à cette position.)

Certains aspects de la définition varient d’un auteur à l’autre, mais ces différences relèvent de la préférence et n’affectent pas la puissance de calcul. Autrement dit, les machines d’un modèle peuvent être simulées ou converties pour s’exécuter sur un autre modèle.

Voici quelques-unes des variantes que vous pourrez rencontrer :

1. Le ruban ne s’étend à l’infini que vers la droite. L’extrémité gauche est le point de départ de la tête de lecture. Un déplacement vers la gauche à cette extrémité laisse la tête sur la même cellule.
2. Outre « aller à gauche » (L) et « aller à droite » (R), un déplacement de la tête peut être « ne pas bouger » (N).
3. Au lieu de déplacer la tête de lecture, le déplacement décale le ruban lui-même, de sorte que les directions L et R sont inversées. (Décaler le ruban vers la gauche revient à déplacer la tête vers la droite.)
4. La machine ne peut s’arrêter que dans l’un de deux états : un état désigné comme état d’acceptation, ou un autre désigné comme état de rejet. Ces états n’ont pas de transition sortante. Tous les autres états doivent définir une transition pour chaque symbole.

Le simulateur a été conçu en tenant compte de ces considérations, entre autres.

1. Limiter le ruban s’est révélé peu pratique : il fallait souvent marquer l’extrémité gauche par un symbole et écrire les nombres à l’envers. À l’inverse, les machines conçues pour un ruban infini à droite fonctionnent sur un ruban doublement infini avec peu ou pas de modification.
2. Comparé à L et R, « ne pas bouger » (N) semble rarement utilisé. Il a été omis pour l’instant, par souci de simplicité conceptuelle.
3. Il est plus intuitif de définir la cellule courante directement en déplaçant la tête de lecture. Turing suit également cette convention. (La visualisation reste toutefois centrée sur la tête, pour éviter qu’elle ne sorte du champ.)
4. La convention acceptation/rejet reste utilisable ; elle n’est simplement pas obligatoire. Le simulateur accepte d’ailleurs un raccourci commode, illustré par certains exemples : omettre l’état de rejet et toutes les transitions qui y mènent, et traiter un arrêt sur un état non acceptant comme une transition de rejet implicite. Cela réduit le code répétitif et donne un diagramme plus lisible.