Vidéo de présentation du concept de machine de Turing :
Comment réaliser une machine de Turing universelle :
Activité "mise en oeuvre de la machine de Turing" : fichier PDF
Machine de Turing, feuille vierge : fichier PDF
Lien vers le simulateur de machine de Turing en ligne
Quelques exemples de MT à tester dans le simulateur :
print('BONJOUR') :
; BONJOUR ; Imprime BONJOUR sur un ruban vide q0 _ B d q1 q1 _ O d q2 q2 _ N d q3 q3 _ J d q4 q4 _ O d q5 q5 _ U d q6 q6 _ R d halt
Addition binaire :
; Addition de deux nombres binaires de même taille ; Alphabet utilisé : _ 0 1 + = A B ; Le ruban initial doit contenir le premier nombre binaire sur N bits ; suivi du caractère "+" ; puis le deuxième nombre binaire sur N bits suivi du caractère "=" ; puis N+1 caractères "0" ; (voir exemple fourni) ; $INITIAL_TAPE:01010101+00110110=000000000 q0 0 0 d q0 q0 1 1 d q0 q0 A A d q0 q0 B B d q0 q0 + + g q1 q1 0 A d q2 q1 1 B d q3 q1 A A g q1 q1 B B g q1 q1 _ _ d q14 q2 + + d q2 q2 0 0 d q2 q2 1 1 d q2 q2 A A d q2 q2 B B d q2 q2 = = g q4 q3 + + d q3 q3 0 0 d q3 q3 1 1 d q3 q3 A A d q3 q3 B B d q3 q3 = = g q5 q4 0 A d q6 q4 1 B d q7 q4 A A g q4 q4 B B g q4 q4 + + g q4 q5 0 A d q7 q5 1 B d q8 q5 A A g q5 q5 B B g q5 q5 + + g q5 q6 = = d q6 q6 0 0 d q6 q6 1 1 d q6 q6 A A d q6 q6 B B d q6 q6 _ _ g q9 q7 = = d q7 q7 0 0 d q7 q7 1 1 d q7 q7 A A d q7 q7 B B d q7 q7 _ _ g q10 q8 = = d q8 q8 0 0 d q8 q8 1 1 d q8 q8 A A d q8 q8 B B d q8 q8 _ _ g q11 q9 A A g q9 q9 B B g q9 q9 0 A g q13 q9 1 B g q13 q10 A A g q10 q10 B B g q10 q10 0 B g q13 q10 1 A g q12 q11 A A g q11 q11 B B g q11 q11 0 A g q12 q11 1 B g q12 q12 0 1 g q13 q12 1 0 g q12 q13 0 0 g q13 q13 1 1 g q13 q13 A A g q13 q13 B B g q13 q13 = = g q13 q13 + + g q13 q13 _ _ d q0 q14 0 0 d q14 q14 1 1 d q14 q14 A 0 d q14 q14 B 1 d q14 q14 + + d q14 q14 = = d q14 q14 _ _ g halt
Comptage du nombre d'occurrences d'un caractère dans un texte :
; Comptage du nombre de B dans un mot comportant des A et des B ; Alphabet utilisé : _ A B 1 0 # @ ; Exemple de mot d'entrée : 0#AAABBBAAABAB q0 _ _ g q4 q0 0 0 d q0 q0 1 1 d q0 q0 # # d q0 q0 A A d q0 q0 B @ g q1 q0 @ @ d q0 q1 A A g q1 q1 B B g q1 q1 @ @ g q1 q1 # # g q2 q2 0 1 d q3 q2 1 0 g q2 q2 _ 1 d q3 q3 0 0 d q3 q3 1 1 d q3 q3 # # d q3 q3 A A d q3 q3 @ @ d q0 q3 _ _ g q4 q4 0 0 g q4 q4 1 1 g q4 q4 A A g q4 q4 @ B g q4 q4 # # g q4 q4 _ _ d halt
Division par deux avec reste :
; Division par deux avec reste ; Alphabet utilisé : _ 0 1 ; Le ruban initial doit contenir un nombre binaire quelconque ; Après exécution le ruban contient le quotient et le reste, séparés par un "vide" ; $INITIAL_TAPE:101010011011 q0 0 0 d q0 q0 1 1 d q0 q0 _ _ g q1 q1 0 _ d q2 q1 1 _ d q3 q2 _ 0 d halt q3 _ 1 d halt
Duplicateur de nombre binaire :
; Crée une copie d'un nombre binaire quelconque ; Alphabet utilisé : _ 0 1 A B a b # ; Le ruban doit contenir le nombre binaire à copier suivi du caractère # ; Exemple de mot d'entrée : 101100111000# q0 0 a d q1 q0 1 b d q2 q0 # # d q4 q1 0 0 d q1 q1 1 1 d q1 q1 # # d q1 q1 A A d q1 q1 B B d q1 q1 _ A g q3 q2 0 0 d q2 q2 1 1 d q2 q2 # # d q2 q2 A A d q2 q2 B B d q2 q2 _ B g q3 q3 0 0 g q3 q3 1 1 g q3 q3 # # g q3 q3 A A g q3 q3 B B g q3 q3 a 0 d q0 q3 b 1 d q0 q3 _ _ d q0 q4 A 0 d q4 q4 B 1 d q4 q4 _ _ d halt
Incrémenteur binaire :
; Incrémenteur binaire ; Attend un nombre binaire quelconque dans le ruban initial ; Alphabet utilisé : _ 0 1 + = A B ;$INITIAL_TAPE:1111111 q0 0 0 d q0 q0 1 1 d q0 q0 _ _ g q1 q1 0 1 g q2 q1 1 0 g q1 q1 _ 1 d halt q2 0 0 g q2 q2 1 1 g q2 q2 _ _ d halt
Incrémenteur décimal :
; Incrémenteur décimal ; Attend un nombre binaire quelconque dans le ruban initial ; Alphabet utilisé : _ 0 1 2 3 4 5 6 7 8 9 ;$INITIAL_TAPE:1024 q0 0 0 d q0 q0 1 1 d q0 q0 2 2 d q0 q0 3 3 d q0 q0 4 4 d q0 q0 5 5 d q0 q0 6 6 d q0 q0 7 7 d q0 q0 8 8 d q0 q0 9 9 d q0 q0 _ _ g q1 q1 0 1 g q2 q1 1 2 g q2 q1 2 3 g q2 q1 3 4 g q2 q1 4 5 g q2 q1 5 6 g q2 q1 6 7 g q2 q1 7 8 g q2 q1 8 9 g q2 q1 9 0 g q1 q1 _ 1 d halt q2 0 0 g q2 q2 1 1 g q2 q2 2 2 g q2 q2 3 3 g q2 q2 4 4 g q2 q2 5 5 g q2 q2 6 6 g q2 q2 7 7 g q2 q2 8 8 g q2 q2 9 9 g q2 q2 _ _ d halt