GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Solution : machine de Turing d'un additionneur ======

Solution possible

<code lang-none>
; Machine additionnant deux nombres en décimal
; il faut écrire par exemple 45+17

; état initial
; insère un 0 au besoin
init _ 0 * dg
init * * * dg

; dg: décale d'une case à gauche
; tout le premier mot
dg 0 * l eg0    ; eg(i) pour écrire le i à gauche
dg 1 * l eg1
dg 2 * l eg2
dg 3 * l eg3
dg 4 * l eg4
dg 5 * l eg5
dg 6 * l eg6
dg 7 * l eg7
dg 8 * l eg8
dg 9 * l eg9
dg + * r cd
dg _ * l nettoiel
eg0 * 0 r md   ; md: simple mouvement à droite
eg1 * 1 r md
eg2 * 2 r md
eg3 * 3 r md
eg4 * 4 r md
eg5 * 5 r md
eg6 * 6 r md
eg7 * 7 r md
eg8 * 8 r md
eg9 * 9 r md
md * # r dg

; état nettoiel : va vers la gauche en nettoyant
; enlève le +
; quand rencontre un #, lance une procédure consistant à décaler le # à gauche 
nettoiel + _ l nettoiel
nettoiel # # l dd
nettoiel _ _ r halt
nettoiel * * l nettoiel

; cd : cherche la colonne de droite
cd _ _ l transport
cd * * r cd

; transport
; cette partie est longue parce qu'on doit transporter un chiffre,
; et pour ce souvenir du chiffre transporté, il faut un état différent par chiffre :
; t0 pour le transport de 0
; t1 pour le transport de 1...
; puis on doit détecter qu'on a passé le # et qu'on doit sommer. Nouvel état
; tt0 pour transport de 0 après #
; tt1 pour transport de 1 après #...
; enfin il faut envisager tous les cas constituant la table d'addition :
; tt2 tombant sur un 4, cela fait 6 et on peut repartir à droite pour le prochain
; tt4 tombant sur un 9 cela fait 3 et il faut propager la retenue de 1
; si transport tombe sur +, c'est que le nombre de droite est fini et qu'on peut lancer le nettoyage
transport + _ l nettoiel
transport 0 _ l t0
transport 1 _ l t1
transport 2 _ l t2
transport 3 _ l t3
transport 4 _ l t4
transport 5 _ l t5
transport 6 _ l t6
transport 7 _ l t7
transport 8 _ l t8
transport 9 _ l t9
t0 # * l tt0
t0 * * l t0
t1 # * l tt1
t1 * * l t1
t2 # * l tt2
t2 * * l t2
t3 # * l tt3
t3 * * l t3
t4 # * l tt4
t4 * * l t4
t5 # * l tt5
t5 * * l t5
t6 # * l tt6
t6 * * l t6
t7 # * l tt7
t7 * * l t7
t8 # * l tt8
t8 * * l t8
t9 # * l tt9
t9 * * l t9
tt0 * * r lfdr
tt1 _ 1 r lfdr
tt1 0 1 r lfdr   ; lfdr: recherche de dièse sur la doite
tt1 1 2 r lfdr
tt1 2 3 r lfdr
tt1 3 4 r lfdr
tt1 4 5 r lfdr
tt1 5 6 r lfdr
tt1 6 7 r lfdr
tt1 7 8 r lfdr
tt1 8 9 r lfdr
tt1 9 0 l tt1
tt2 _ 2 r lfdr
tt2 0 2 r lfdr
tt2 1 3 r lfdr
tt2 2 4 r lfdr
tt2 3 5 r lfdr
tt2 4 6 r lfdr
tt2 5 7 r lfdr
tt2 6 8 r lfdr
tt2 7 9 r lfdr
tt2 8 0 l tt1
tt2 9 1 l tt1
tt3 _ 3 r lfdr
tt3 0 3 r lfdr
tt3 1 4 r lfdr
tt3 2 5 r lfdr
tt3 3 6 r lfdr
tt3 4 7 r lfdr
tt3 5 8 r lfdr
tt3 6 9 r lfdr
tt3 7 0 l tt1
tt3 8 1 l tt1
tt3 9 2 l tt1
tt4 _ 4 r lfdr
tt4 0 4 r lfdr
tt4 1 5 r lfdr
tt4 2 6 r lfdr
tt4 3 7 r lfdr
tt4 4 8 r lfdr
tt4 5 9 r lfdr
tt4 6 0 l tt1
tt4 7 1 l tt1
tt4 8 2 l tt1
tt4 9 3 l tt1
tt5 _ 5 r lfdr
tt5 0 5 r lfdr
tt5 1 6 r lfdr
tt5 2 7 r lfdr
tt5 3 8 r lfdr
tt5 4 9 r lfdr
tt5 5 0 l tt1
tt5 6 1 l tt1
tt5 7 2 l tt1
tt5 8 3 l tt1
tt5 9 4 l tt1
tt6 _ 6 r lfdr
tt6 0 6 r lfdr
tt6 1 7 r lfdr
tt6 2 8 r lfdr
tt6 3 9 r lfdr
tt6 4 0 l tt1
tt6 5 1 l tt1
tt6 6 2 l tt1
tt6 7 3 l tt1
tt6 8 4 l tt1
tt6 9 5 l tt1
tt7 _ 7 r lfdr
tt7 0 7 r lfdr
tt7 1 8 r lfdr
tt7 2 9 r lfdr
tt7 3 0 l tt1
tt7 4 1 l tt1
tt7 5 2 l tt1
tt7 6 3 l tt1
tt7 7 4 l tt1
tt7 8 5 l tt1
tt7 9 6 l tt1
tt8 _ 8 r lfdr
tt8 0 8 r lfdr
tt8 1 9 r lfdr
tt8 2 0 l tt1
tt8 3 1 l tt1
tt8 4 2 l tt1
tt8 5 3 l tt1
tt8 6 4 l tt1
tt8 7 5 l tt1
tt8 8 6 l tt1
tt8 9 7 l tt1
tt9 _ 9 r lfdr
tt9 0 9 r lfdr
tt9 1 0 l tt1
tt9 2 1 l tt1
tt9 3 2 l tt1
tt9 4 3 l tt1
tt9 5 4 l tt1
tt9 6 5 l tt1
tt9 7 6 l tt1
tt9 8 7 l tt1
tt9 9 8 l tt1

; lfdr recherche le dièse sur la droite
lfdr # # l copd
lfdr * * r lfdr

; copd : copie à droite en laissant un dièse
copd _ # r copd0
copd 0 # r copd0
copd 1 # r copd1
copd 2 # r copd2
copd 3 # r copd3
copd 4 # r copd4
copd 5 # r copd5
copd 6 # r copd6
copd 7 # r copd7
copd 8 # r copd8
copd 9 # r copd9
copd0 * 0 r cd
copd1 * 1 r cd
copd2 * 2 r cd
copd3 * 3 r cd
copd4 * 4 r cd
copd5 * 5 r cd
copd6 * 6 r cd
copd7 * 7 r cd
copd8 * 8 r cd
copd9 * 9 r cd

; dd : redécale à droite
; on prend le chiffre, on laisse un # et on écrit juste à droite
dd _ _ r edd
dd 0 # r ed0
dd 1 # r ed1
dd 2 # r ed2
dd 3 # r ed3
dd 4 # r ed4
dd 5 # r ed5
dd 6 # r ed6
dd 7 # r ed7
dd 8 # r ed8
dd 9 # r ed9
edd * _ r halt
ed0 * 0 l nettoiel
ed1 * 1 l nettoiel
ed2 * 2 l nettoiel
ed3 * 3 l nettoiel
ed4 * 4 l nettoiel
ed5 * 5 l nettoiel
ed6 * 6 l nettoiel
ed7 * 7 l nettoiel
ed8 * 8 l nettoiel
ed9 * 9 l nettoiel
</code>