Les dattes à Dattier
Re: Les dattes à Dattier
Une notion d'info théorique, tu verras ça normalement en 1A/L3 dans une école qui enseigne l'info théorique.
https://fr.wikipedia.org/wiki/D%C3%A9cidabilit%C3%A9
En gros, pour faire simple, une question décidable est une question à laquelle on peut répondre "oui ou non". Par exemple "pour p donné, p est-il premier ?" est décidable. Par contre, "pour X un programme informatique, X va-t-il se terminer" est a priori indécidable.
(Je reste flou sur le sens précis des termes. En général on enseigne ça avec les machines de Turing.)
@Hibiscus : t'es sûr que c'est au programme de MPSI (ou même de prépa), la décidabilité ? Moi pas...
https://fr.wikipedia.org/wiki/D%C3%A9cidabilit%C3%A9
En gros, pour faire simple, une question décidable est une question à laquelle on peut répondre "oui ou non". Par exemple "pour p donné, p est-il premier ?" est décidable. Par contre, "pour X un programme informatique, X va-t-il se terminer" est a priori indécidable.
(Je reste flou sur le sens précis des termes. En général on enseigne ça avec les machines de Turing.)
@Hibiscus : t'es sûr que c'est au programme de MPSI (ou même de prépa), la décidabilité ? Moi pas...
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.
Re: Les dattes à Dattier
Même si la chaîne $ s $ de Hibiscus avait un sens mathématique, la question serait triviale étant donné que tout langage fini est décidable.
Pour formaliser, on suppose qu’il existe un théorème (prédicat sans variables libres) $ P $ de la théorie ZF qui exprime l’existence de Dieu. L’ensemble de Hibiscus est bien défini par un axiome de compréhension:
$
A = \{ \{ x \in \{\emptyset\} | P \} \}
$ en utilisant évidemment la construction de Von Neumann pour les entiers: $ 0 = \emptyset $, $ 1 = \{ \emptyset \} $. Alors comme je l’ai dit: $ A $ est de cardinal 1 donc décidable.
Pour mieux comprendre pourquoi c’est vrai: impossible de savoir a priori si $ P $ ou $ \lnot P $ est prouvable dans ZF. Mais dans un modèle de ZF donné, le langage $ A $ est égal soit à $ \{0\} $, soit à $ \{1\} $ et est dans chaque cas trivialement décidable. La propriété « $ A $ est décidable » étant vraie dans tout modèle de ZF, elle est prouvable dans ZF d’après le théorème de complétude.
Maintenant, on est sur un forum de classes prepas donc ça serait pas mal que les énoncés:
- aient un sens
- soient au moins compréhensibles par des gens en prépa (« rubrique des rentrées en MPSI » lol)
Si la preuve d’un énoncé est de surcroit accessible en prépa, ça devient un bon énoncé. Notons que l’énoncé d’Hibiscus ne vérifie aucun des précédents critères, en plus d'être absolument trivial (preuve en 5 mots).
Pour formaliser, on suppose qu’il existe un théorème (prédicat sans variables libres) $ P $ de la théorie ZF qui exprime l’existence de Dieu. L’ensemble de Hibiscus est bien défini par un axiome de compréhension:
$
A = \{ \{ x \in \{\emptyset\} | P \} \}
$ en utilisant évidemment la construction de Von Neumann pour les entiers: $ 0 = \emptyset $, $ 1 = \{ \emptyset \} $. Alors comme je l’ai dit: $ A $ est de cardinal 1 donc décidable.
Pour mieux comprendre pourquoi c’est vrai: impossible de savoir a priori si $ P $ ou $ \lnot P $ est prouvable dans ZF. Mais dans un modèle de ZF donné, le langage $ A $ est égal soit à $ \{0\} $, soit à $ \{1\} $ et est dans chaque cas trivialement décidable. La propriété « $ A $ est décidable » étant vraie dans tout modèle de ZF, elle est prouvable dans ZF d’après le théorème de complétude.
Maintenant, on est sur un forum de classes prepas donc ça serait pas mal que les énoncés:
- aient un sens
- soient au moins compréhensibles par des gens en prépa (« rubrique des rentrées en MPSI » lol)
Si la preuve d’un énoncé est de surcroit accessible en prépa, ça devient un bon énoncé. Notons que l’énoncé d’Hibiscus ne vérifie aucun des précédents critères, en plus d'être absolument trivial (preuve en 5 mots).
ENS Lyon
Ingénieur de recherche
Ingénieur de recherche
Re: Les dattes à Dattier
Non non, ce n'est pas même au programme de l'option informatique. C'est une tentative d'humour, je dirais.
Professeur de mathématiques et d'informatique en PCSI au lycée Champollion.
Re: Les dattes à Dattier
Ou plutôt un aperçu de logique intuitionniste…
Re: Les dattes à Dattier
Pas besoin de logique intuitionniste pour parler de décidabilité (et vice-versa).
La vache, il est abyssal cet humour... (et si c'est moi qui dit ça faut s'inquiéter)Simon Billouet a écrit : ↑02 juil. 2018 13:33Non non, ce n'est pas même au programme de l'option informatique. C'est une tentative d'humour, je dirais.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.
Re: Les dattes à Dattier
La fonction indicatrice de $ \mathbb{Q} $ (ni miraculeuse, ni algébrique).
ENS Lyon
Ingénieur de recherche
Ingénieur de recherche
Re: Les dattes à Dattier
Ah oui en effet, remplace par $ x-1 $ par $ x+2 $ alors
ENS Lyon
Ingénieur de recherche
Ingénieur de recherche
Re: Les dattes à Dattier
C'est très malin. Joli exercice pour un taupin.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.
Re: Les dattes à Dattier
Puisque 0 est un polynôme de degré inférieur ou égal à 1, la même démonstration que le 153 ne suffit pas ?
2017/2018: MPSI
2018/2019: MP* / Lycée Fermat
2018/2019: MP* / Lycée Fermat