Calculabilité complexité

Quelques exercices de la séance 1

• Décalage à droite (B,a,b)
• Successeur (B,1)
• Prédécesseur (B,1)
• Double (B,1)
• Addition (B,1)
• +1 entiers en notation binaire (B,0,1)
• ×2 entiers en notation décimale (B,0…9)
• Mots miroirs sur (B,a,b,c)
• anbn (B,a,b) avec ou sans extension
• anbn (0,1) machine simple