Simuler une machine à ruban minuscule

Les règles. La tête part de la case la plus à droite (poids faible).

• sur un '1' : écrire '0', se déplacer d'une case à gauche, continuer ;
• sur un '0' : écrire '1', s'arrêter ;
• sortie du ruban à gauche : ajouter une case '1' devant, s'arrêter.

C'est la retenue de l'addition binaire du chapitre 1, réduite à un jeu de trois règles.

def incrementer_ruban(ruban):
    """Incremente de 1 le nombre binaire ecrit sur le ruban.

    Le ruban est une chaine de '0' et de '1', poids fort a gauche.
    Precondition  : ruban est non vide et ne contient que '0' et '1'.
    Postcondition : la valeur codee augmente exactement de 1.
    """
    r = list(ruban)
    i = len(r) - 1
    while i >= 0 and r[i] == "1":
        r[i] = "0"
        i = i - 1
    if i < 0:
        r = ["1"] + r
    else:
        r[i] = "1"
    return "".join(r)

La validation.

assert incrementer_ruban("0") == "1"
assert incrementer_ruban("1") == "10"
assert incrementer_ruban("1011") == "1100"
assert incrementer_ruban("1111") == "10000"

for n in range(0, 5000):
    assert depuis_base(incrementer_ruban(vers_base(n, 2)), 2) == n + 1

Les quatre cas nommés et les $5000$ valeurs passent. Les deux derniers cas nommés sont les intéressants : "1111" est le cas où le ruban doit s'allonger, et c'est le seul endroit où la troisième règle sert.

Le lien avec le cours. Cette machine n'a ni variable nommée, ni fonction, ni expression arithmétique : un ruban, une position, trois règles. Et pourtant elle calcule. C'est l'idée de Turing en 1936 — le repère historique du chapitre : la puissance de calcul ne vient pas de la richesse du langage, mais de la possibilité de lire, d'écrire et de se déplacer selon des règles. Hors programme, évidemment ; mais c'est le raccourci le plus court vers la question « que peut faire une machine ? ».