Partie MT = Machines de Turing, Calculabilité, (In)Décidabilité
  1. Notes de cours, à compléter (.pdf)

  2. Notes de cours, version complète disponible une semaine avant l'examen (.pdf)
  1. Une utilisation inattendue des Busy Beaver en Mathématiques

    Si la machine s'arrête la théorie mathématique basée sur l'axiome du choix est contradictoire.

    Ceci n'est pas un dévideur de scotch mais une Machine de Turing

    L'article scientifique d'A.Yedidia et S.Aaronson du MIT (en anglais) et l'article de vulgarisation (en français)

  2. Une utilisation inattendue des machines de Turing en sciences cognitives (43 min 25s)

    [La] perception du hasard [par le cerveau humain] par Nicolas Gauvrit.

  3. Une émission de France Culture sur « Ce que (peut / ne peut pas) l'informatique » (35 min)

    Les invités : Yann Le Cun & Gérard Berry

  4. Une chronique de G.Berry sur France Culture « Une machine peut-elle penser ? » (4 min)
    Extrait : « Dans les années 1980-2010, les mauvaises langues disaient que l'Intelligence Artifielle c'est ce que l'informatique ne savait pas faire. »    Gérard Berry, Professeur au Collège de France, titulaire de la chaire : algorithmiques, machines et langages.

  5. Les castors affairés (Busy Beaver k)
    Un Busy Beaver est une machine de Turing opérant sur l'alphabet binaire {0,1} qui, à partir d'un ruban vierge, ne fait rien d'utile -- elle déplace juste des batonnets (les 1) d'où le nom de castors affairés -- puis s'arrête.

    BBk est la MT à k états qui fait le plus d'étapes avant de s'arrêter.

    Exemples :
    • BB4 fait 107 pas avant de s'arrêter (trace d'exécution)
    • BB6 fait 3.515 x 1018267 pas avant de s'arrêter (trace d'exécution interrompue ~13Mo)
Responsable du site : Michaël PÉRIN