Ce programme fait une récursion infinie, sans stack-overflow. Il peut boucler jusqu'à la fin des temps.
2- Il est démontré ET il a beaucoup d'intérêts.
Le problème, car il y en a un, c''est qu'il semble que tu n'as aucune formation post-bac en maths ni en informatique, et que donc
a/ le concept de preuve par l'absurde t'échappe
b/ tu n'as jamais eu à faire de preuve qui se ramène au problème de l'arrêt.
Je crois avoir saisi ton problème, alors j'y vais simplement:
a/ Dans cette preuve par l'absurde, il n'y a même pas besoin de programmer la fonction halt ou de dire comment on peut la programmer, l'instancier. Le simple fait de dire "elle existe" est une information suffisante pour faire la preuve, c'est tout. C'est comme dire "imagine le plus grand nombre qui exiite. Ajoute lui "1". Alors on a un nombre plus grand que le plus grand nombre qui existe. Donc y a pas de plus grand nombre".
Tu nous demande si ce nombre est pair ou impair, et on te dit "ca n'a pas de sens, vu qu'il n'existe pas !". Et au bout de 20 messages et 4 liens wikipedia vers la preuve formelle, je comprend leur désarroi et ton niveau en sciences.
b/ Enfin, avec une formation en informatique, tu verrais plein de problèmes qui correspondent au problème de l'arrèt, En dans ces cas là on dit "hophop ! stop ! pas besoin de continuer, on a la preuve qu'on pourra jamais écrire cet algorithme".
Ici, c'est comme toujours "on formalise le problème, on se dit qu'il ressemble a un autre, et on regarde si cet autre est soluble, et si oui, est-ce qu'on peu le résoudre facilement."
T'as plein de problèmes qui ont une solution très dure à calculer, ou qui n'ont pas de solution. Alors pour éviter de calculer les solutions qui n'existent pas ou qui prennent 10 ans à calculer, on dit "c'est comme le problème de l'arrêt" ou "c'est comme le voyageur de commerce", et *tout le monde* est content.
Et si t'es au lycée et que t'aimes pas les maths, ne va pas faire d'info à la fac.
[^] # Re: Halting problem
Posté par Axioplase ıɥs∀ (site web personnel) . En réponse au journal Déterminer le domaine d'un programme. Évalué à 4.
(let loop ()
(loop))
Ce programme fait une récursion infinie, sans stack-overflow. Il peut boucler jusqu'à la fin des temps.
2- Il est démontré ET il a beaucoup d'intérêts.
Le problème, car il y en a un, c''est qu'il semble que tu n'as aucune formation post-bac en maths ni en informatique, et que donc
a/ le concept de preuve par l'absurde t'échappe
b/ tu n'as jamais eu à faire de preuve qui se ramène au problème de l'arrêt.
Je crois avoir saisi ton problème, alors j'y vais simplement:
a/ Dans cette preuve par l'absurde, il n'y a même pas besoin de programmer la fonction halt ou de dire comment on peut la programmer, l'instancier. Le simple fait de dire "elle existe" est une information suffisante pour faire la preuve, c'est tout. C'est comme dire "imagine le plus grand nombre qui exiite. Ajoute lui "1". Alors on a un nombre plus grand que le plus grand nombre qui existe. Donc y a pas de plus grand nombre".
Tu nous demande si ce nombre est pair ou impair, et on te dit "ca n'a pas de sens, vu qu'il n'existe pas !". Et au bout de 20 messages et 4 liens wikipedia vers la preuve formelle, je comprend leur désarroi et ton niveau en sciences.
b/ Enfin, avec une formation en informatique, tu verrais plein de problèmes qui correspondent au problème de l'arrèt, En dans ces cas là on dit "hophop ! stop ! pas besoin de continuer, on a la preuve qu'on pourra jamais écrire cet algorithme".
Ici, c'est comme toujours "on formalise le problème, on se dit qu'il ressemble a un autre, et on regarde si cet autre est soluble, et si oui, est-ce qu'on peu le résoudre facilement."
T'as plein de problèmes qui ont une solution très dure à calculer, ou qui n'ont pas de solution. Alors pour éviter de calculer les solutions qui n'existent pas ou qui prennent 10 ans à calculer, on dit "c'est comme le problème de l'arrêt" ou "c'est comme le voyageur de commerce", et *tout le monde* est content.
Et si t'es au lycée et que t'aimes pas les maths, ne va pas faire d'info à la fac.