Une machine de Turing en Python

Une machine de Turing en Python. Une machine de Turing possède un ruban infini de cases, une tête de lecture, un état, et une table de règles : pour chaque couple (état, symbole lu), la règle indique le symbole à écrire, le déplacement (-1 à gauche, +1 à droite) et le nouvel état. La machine s'arrête dans l'état "fin". On représente le ruban par un dictionnaire position -> symbole ; une case absente contient le blanc " ".

• Écrire une fonction executer(regles, mot, position, etat) qui écrit mot sur le ruban à partir de la case $0$, place la tête en position, applique les règles jusqu'à l'état "fin", puis renvoie le contenu non blanc du ruban, lu de gauche à droite.
• La machine suivante ajoute $1$ à un nombre écrit en binaire ; la tête part sur le dernier chiffre, dans l'état "retenue".

incremente = {
    ("retenue", "1"): ("0", -1, "retenue"),
    ("retenue", "0"): ("1", -1, "fin"),
    ("retenue", " "): ("1", -1, "fin"),
}

Dérouler l'exécution à la main sur 1011, puis vérifier avec la fonction. Que donne-t-elle sur 111 ?

• Écrire la table d'une machine qui inverse tous les bits d'un mot (0 devient 1 et réciproquement), la tête partant du premier chiffre.
• En quoi la fonction executer illustre-t-elle l'idée de machine universelle ?