Je suis en plein dans la calculabilité en ce moment (partie D du programme du concours d'entrée à Cachan). En fait, pour l'instant, je suis plutôt au niveau des prérequis, c'est-à-dire les langages rationnels et hors-contexte (partie C1 à C3).

J'ai appris ce qu'est un automate à pile ; je trouve ça merveilleux. Cela faisait longtemps que je n'avais pas pris un tel plaisir à travailler ; j'ai l'impression de trouver du sens dans ce que j'apprends.

J'attaque les machines de Turing demain. Ce soir, il est trop tard.

PS : ce blog devient un peu "3615 je raconte ma vie", ce que je déteste franchement à la vérité. Seulement j'ai 25 000 trucs à faire en ce moment, alors honnêtement, j'aimerais vraiment vous expliquer ce qu'est un automate à pile, et en quoi il est merveilleux qu'un automate à deux piles soit beaucoup plus puissant qu'un automate à une pile[1], mais si vous voulez vraiment le savoir, achetez Introduction à la calculabilité de Pierre Wolper chez Dunod, et lisez le chapitre 4 ; là, je n'ai pas le temps.

Notes

[1] Un automate à deux piles est aussi puissant qu'une machine de Turing ; un automate à une pile se contente de reconnaître les langages algébriques.