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 machines de Turing en sciences cognitives (43 min 25s)

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

  2. 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

  3. 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.
  4. 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