Archive
Machine de Turing ? Automates finis ? à pile ? (Visite guidée dans le bestiaire informatique)
par Nicolas Schabanel
mercredi 15 février 2006
Conférencier
 |
Nicolas Schabanel Chercheur à l'ENS Lyon
Site : http://perso.ens-lyon.fr/nicolas.schabanel Email : nicolas.schabanel@ens-lyon.fr |
Résumé
L'informatique est née sur le papier au début des années 1930 avec les travaux de Alonzo Church, Kurt Gödel et Alan Turing, et ne fut réalisée effectivement qu'à la fin de la seconde guerre mondiale non pas à cause de problèmes techniques mais parce qu'il y avait enfin des raisons de réaliser les ordinateurs : décrypter les codes allemands en vue du débarquement (avec les travaux de l'équipe d'Alan Turing) et mettre au point l'arme atomique (avec les travaux de l'équipe de von Neumann). Durant ces années, différents modèles de ce que pourrait être un ordinateur ont été proposés : les automates finis (qui ont une mémoire finie), les automates à pile (qui utilisent une pile pour stocker leur information), et les machines de Turing (modèle théorique des ordinateurs actuels). Ces différents engins mathématiques ont différentes capacités de calcul que nous explorerons ensemble sur des exemples très simples. Ils se distinguent en particulier par la façon dont ils mémorisent l'information qu'ils traitent. Leurs puissances de calcul respectives ont été définitivement hiérarchisées par les travaux de Noam Chomsky qui portaient originellement sur la notion de grammaire en linguistique.
Nous verrons dans cet exposé comment ces différentes machines s'articulent et comment chacune a trouvé sa place dans le monde informatique qui nous entoure.
Vidéos & transparents de la conférence
- Vidéo à télécharger : Conférence et questions (RealMedia converti en mp4)
Plan du séminaire
- Qu'est-ce que l'informatique ?
- Automate fini et reconnaissance de langages
- Automate à pile et reconnaissance de langages
- Automate à pile et calculs
Mots clés : Machine de Turing, Automate fini, Automate à pile, Modèle théorique de l'ordinateur, Alonzo Church, Kurt Gödel, Alan Mathison Turing, John von Neumann, Noam Chomsky, Grammaire, Sémantique, Stephen Cole Kleene, Lemme de la pompe
