• l'application d'une expression e1 à une expression e2, notée e1(e2);
  
  
• une fonction attendant un paramètre x et dont le résultat est calculé par une expression e, notée λ.x.e, à rapprocher d'une fonction anonyme Python lambda x: e;
  
  
• une référence à un paramètre x.
  

• λx.x
  
  
• λx.λy.x
  
  
• λf.λg.λx.g(f(x))

• un ruban de mémoire infini dont le contenu peut être consulté et modifié,
  
  
• et une machine se déplaçant le long de ce ruban et en modifiant le contenu en fonction de quelques règles très simples constituant le programme de cette machine.

• une instruction d'écriture, indiquant ce qui doit être écrit à la position actuelle du ruban à la place de l'imformation actuelle;
  
  
• une instruction de déplacement, indiquant s'il faut déplacer la machine le long du ruban et dans quel sens;
  
  
• l'état dans lequel passera la machine après cette étape.
  

1. d'abord se déplacer jusqu'à l'extrémité droite, 
2. puis ajouter 1 au bit de poids faible, et revenir vers la gauche autant que nécessaire pour propager les retenues.

• un état de départ A pour la première phase de déplacement, 
• un état B pour la phase d'incrément,
•  et un état final F indiquant que le calcul est terminé. 

• Un état de la machine est identifié par une chaîne de caractères.
  
  
• Le symbole écrit dans une case du ruban est représenté par une chaîne de caractères.
  
  
• L'ensemble des règles de transition de la machine est matérialisé par un dictionnaire dont les clés sont les états. Consulter ce dictionnaire pour un état donné fournit l'ensemble des règles applicables à partir de cet état, à nouveau sous la forme d'un dictionnaire, dont les clés sont les symboles manipulés par la machine et les valeurs sont les actions associées.
  
  
• Les actions à effectuer à la lecture d'un symbole donné dans un état donné sont représentées par un triplet (e,d,s) où :
• e est le symbole à écrire (une  chaîne de caractères);
• d est le déplacement éventuel: 
•      —1 pour aller à gauche,
        0 pour ne pas bouger,
        1 pour aller à droite;
• s est l'état suivant (une chaîne de caractères).
  

• L'indice i = 3, correspondant à l'occurrence de ‘a' à l'indice j=7 dans le motif, est hors jeu:
           notre exploration était déjà arrivée i  = 5 et ne fait que progresser.
• L'indice i = 10, correspondant à l'occurrence de 'a' à l'indice j = 0 dans le motif, serait tentant car c'est lui qui fait progresser le plus vite dans la lecture du texte. Il risquerait cependant d'aller trop vite et de nous faire manquer une occurrence intermédiaire du motif.

• Si la sous-chaîne commençant à l'indice i est égale au motif cherché, indiquer une occurrence et reprendre à l'indice i+1.
  
  
• Sinon, si l'on a observé une différence entre le caractère à l'indice j du motif et le caractère à l'indice i + j = k du texte, incrémenter i jusqu'à ce que:
• soit i dépasse k, 
• soit le caractère à l'indice k-i du motif soit égal au caractère à l'indice i du texte.

• On va tester l'occurrence du motif m dans le texte t à des positions i de plus en plus grandes, en partant de i=0. Cela n'est pas différent pour l'instant de ce que nous avons fait dans les sections précédentes.
  
  
• Pour une position i donnée, on va comparer les caractères de m et de t de la droite vers la gauche, c'est-à-dire en comparant d'abord m[M-1]
  et t[i+ M — 1], puis m[M — 2] et t[i + M — 2], etc. Il s'agit là du sens inverse de celui utilisé au début de cette séquence. Le changement peut paraître anecdotique, mais en pratique il permet d'avancer plus vite dans certains cas (dont nous discuterons plus loin).
  
  
• Si tous les caractères coïncident, on à trouvé une occurrence. Sinon, soit j l'indice de la première différence, c'est-à-dire le plus grand entier tel que 0 ≤ j < M et m[j] ≠ t[i+j].
  
  Appelons c le caractère t[i+j]. 

• la grandeur j — k où k est le plus grand entier tel que 0 ≤ k < j et m[k] = c, si un tel k existe (de manière à amener un caractère c de m sous le caractère t[i+ j]),
  
  
• la grandeur j + 1 sinon.

    i = 0\n    while i <= len(t) - len(m):

        k = 0\n        for j in range(len(m) - 1, -1, -1):\n

           if t[i + j] != m[j]:\n                k = decalage(d, j, t[i + j])\n                break

         if k == 0:\n          print(\"occurrence à la position\", i)\n            k = 1\n 

       i += k

def table_bm(m):

     d = [{} for _ in range(len(m))]

    for j in range(len(m)):\n        for k in range(j):\n 

            d[j][m[k]] = k

    return d

• 0 (occurrence, qui donne le décalage 1)
• 1 (qui donne le décalage 8),
  
• 9 (décalage 3),
  
• 12 (occurrence, décalage 1),
• 13 (décalage 8),
• 21 (décalage 3),
• 24 (occurrence, décalage 1),
  
• 25 (décalage 8).