Index of /publis/kit-informatique-debranchee-preuve-pb-arret-Turing

[ICO]NameLast modifiedSizeDescription
[PARENTDIR]Parent Directory  -  
[DIR]Logos/2021-03-10 08:37 -  
[ ].gitignore2021-03-10 08:37 7  
[ ]LICENSE2021-03-10 08:37 1.1K 
[TXT]README.md2021-03-10 08:37 3.3K 
[ ]article2.pdf2021-03-10 08:37 243K 
[TXT]def.tex2021-03-10 08:37 3.4K 
[TXT]intro.tex2021-03-10 08:37 68  
[TXT]pack.tex2021-03-10 08:37 698  
[ ]toolkit.pdf2021-03-10 08:37 342K 
[TXT]toolkit.tex2021-03-10 08:37 28K 
# Kit informatique débranchée pour une preuve de l'Indécidabilité du problème de l'arrêt

> Voir cette page : <http://www.irem.univ-bpclermont.fr/Indecidabilite-du-probleme-de-l>.
> Les documents disponibles (mis en ligne le 09 janvier 2020) sont sous licence Creative Commons.

## Documents

Cf `toolkit.tex` et autres fichiers LaTeX présents ici.

---

##  Présentation à Didapro (huitième édition) par Rémy Poulain

Rémy Poulain avait présenté à la conférence Didapro8 en février 2020 dernier à Lille (<https://www.didapro.org/8/>) une activité d'informatique débranchée à faire au niveau lycée, pour faire comprendre cette preuve de l'indécidabilité du problème de l'arrêt, sans faire manipuler de codage de machines de Turing, ou de code Python.

Le tutoriel est encore présent en PDF : <https://www.didapro.org/8/wp-content/uploads/sites/4/2020/01/Didapro_8_paper_17.pdf> et il explique très bien les avantages de l'activité.

> **Une preuve pour le lycée de l'indécidabilité du problème de l'arrêt** Rémy POULAIN (animateur)
>
> L'objectif de l'activité est de faire démontrer par des élèves qu'il existe des problèmes informatiques qui sont indécidables, c'est-à-dire pour lesquels il n'existe pas d'algorithme pour les résoudre. Pour montrer qu'il existe de tels problèmes, l'activité en exhibe un, le problème de l'arrêt : étant donnée une paire représentant l'encodage d'une machine de Turing M et un mot w, l'exécution de M sur l'entrée w s'arrête-t-elle ? L'activité suit la preuve proposée par Turing, mettant ainsi en avant le principe du raisonnement par l'absurde et la notion de disjonction des cas. Tout au long de l'activité, les élèves se servent d'une ardoise préparée par le professeur pour exécuter à la main du code (en Scratch). Ceci permet d'abord de leur faire découvrir des programmes Scratch simples, mais aussi de les familiariser avec un formalisme proche de la machine de Turing (plus précisément d'une machine à registre). Certains de ces programmes simples sont ensuite composés ensemble pour obtenir le résultat d'indécidabilité.

---

## À propos de ce dossier

Je ne suis PAS l'auteur de ce dossier.
Je les ai stocké ici dans un but d'archivage, et pour pouvoir plus facilement les réutiliser si j'en ai le besoin.

### :scroll: Licence ?

Ces documents sont sous licence Creative Commons.

[![made-with-LaTeX](https://img.shields.io/badge/Made%20with-LaTeX-1f425f.svg)](https://www.latex-project.org/)
[![HitCount](http://hits.dwyl.io/Naereen/kit-informatique-debranchee-preuve-pb-arret-Turing.svg)](http://hits.dwyl.io/Naereen/kit-informatique-debranchee-preuve-pb-arret-Turing)
[![Maintenance](https://img.shields.io/badge/Maintained%3F-yes-green.svg)](https://GitHub.com/Naereen/kit-informatique-debranchee-preuve-pb-arret-Turing/graphs/commit-activity)
[![Demandez moi n'importe quoi !](https://img.shields.io/badge/Demandez%20moi-n'%20importe%20quoi-1abc9c.svg)](https://GitHub.com/Naereen/ama.fr)
[![ForTheBadge uses-badges](http://ForTheBadge.com/images/badges/uses-badges.svg)](http://ForTheBadge.com)
[![ForTheBadge uses-git](http://ForTheBadge.com/images/badges/uses-git.svg)](https://GitHub.com/)
[![ForTheBadge built-with-swag](http://ForTheBadge.com/images/badges/built-with-swag.svg)](https://GitHub.com/Naereen/)