Bonjour à tous !  
Je m'appelle Nicolas et je démarre ma première année de DUT informatique.
Il y a pas longtemps mon prof de Mathématiques discrètes nous a parler d'une chose qui a titiller ma curiosité.
Nous parlions des ensembles, et de relation d'appartenance et dans un exemple il a dit qu'il était impossible de créer un programme qui détermine si un autre programme s'arrête ou non. Clairement j'ai pas bien compris en quoi c'est impossible, même dans le contexte.  
 
Il a également fait référence au paradoxe du barbier : "Le conseil municipal d'un village arrête une ordonnance qui enjoint à son barbier (masculin) de raser tous les habitants masculins du village qui ne se rasent pas eux-mêmes et seulement ceux-ci."  
 
Bon maintenant que je suis allé chercher ça sur wikipedia j'ai un bout de réponse pour le barbier (illustation à but didactique du paradoxe de Russell).
 
Mais qu'en est-il de l'infaisabilité d'un tel programme ?  
Merci à qui perdra la raison en répondant à ma question  

Pour le premier, je n'ai pas d'"explication simple
 
pour le second:

• si le barbier se rase lui même, alors il ne doit pas se raser (il ne doit raser QUE ceux qui ne se rasent pas eux même)
• si il ne se rase pas alors il doit se raser ( il doit raser TOUS les homme qui ne se rasent pas)

Salut,
 
Sur Wikipédia il y a ça aussi : http://fr.wikipedia.org/wiki/Probl [...] arr%C3%AAt (Problème de l'arrêt)
Il y a le coin discussion pour débattre : http://fr.wikipedia.org/wiki/Discu [...] arr%C3%AAt
 
Dans le premier paragraphe, il y a écrit qu'il y a des cas de boucle infinie bien identifiables où le programme pourra répondre catégoriquement oui.  
 
La programmation ce n'est pas toujours des algorithmes simples.
Et quand on commence à utiliser la récursivité, les structures de données dynamiques, le programme capable de répondre à la question "ce programme a-t-il une fin ?" n'existe pas.
 
Edit : d'autres trucs intéressants
http://fr.wikipedia.org/wiki/Analy [...] programmes (Analyse statique de programmes)
http://fr.wikipedia.org/wiki/M%C3% [...] ormatique) (Méthode formelle)

Pas besoin de structures complexes,  il faut du non deterministe
 

toute les seconde , ton programme à une chance sur deux de s'arreter, mais avec un  beaucoup  de chance, il peut continuere indefiniment

ca rejoint une problématique similaire : écrire un programme de déterminer si un autre programme est un virus ou pas. C'est pas déterministe. En effet, une combinaison d'actions effectuées peut très bien l'être dans le cadre d'un programme "normal", mais effectuées dans un autre contexte, ça peut être malveillant (ex : suppression de fichiers, envoi d'un carnet d'adresses par mail...).

Merci à tous d'avoir répondu aussi vite ! C'est passionnant tout ça
Je vais surement avoir besoin de plusieurs années pour assimiler correctement cette notion mais je pense avoir compris le problème de l'arrêt dans les grandes lignes.
J'ai quand même du mal a faire le rapprochement avec ceci dans l'étude des ensembles :
X ∈ X et sa "cause à effet"  : X ∉ X