La machine de turing

Pour les machines de Turing, un bon départ est wikipedia...

Une machine de Turing fonctionne comme un magnétophone avec deux améliorations concernant la bande : celle-ci est infinie et est divisée en cases de mêmes tailles.

On fait comme avec un magnétophone, on donne une bande à la machine, on lance la lecture et on attend le résultat.

On attend le résultat retourné en fonction de conditions initialement programmées dans la machine : en fonction d'un symbole lu, on en écrit un autre et on se déplace à gauche ou bien à droite d'une seule case.

Par exemple, on écrit le symbole 0 dans trois cases successives. Puis on dit à la machine que si elle lit un zéro, on le récrit par un 1 et on se déplace à droite d'une case. Alors si on donne la bande avec 3 zéros successifs à la machine, le résultat sera une bande avec trois 1 successifs (pourvu que la lecture commence au 0 le plus à gauche).

Cet exemple implémente le complément à 1, qui est la première étape dans la représentation d'un nombre négatif dans un ordinateur (qui est réalisé par le complément à 2).

Pour une tonne d'exemples implémentés, un bouquin vient de sortir, aux éditions cépaduès.

Bonne chance !

Qouic.