Les dattes à Dattier

Un problème, une question, un nouveau théorème ?

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par siro » 02 juil. 2018 10:33

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...
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 0

Inscription : 19 avr. 2015 00:08

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par darklol » 02 juil. 2018 11:28

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).
ENS Lyon
Ingénieur de recherche

Messages : 109

Inscription : 18 avr. 2018 19:17

Profil de l'utilisateur : Enseignant (CPGE)

Re: Les dattes à Dattier

Message par Simon Billouet » 02 juil. 2018 13:33

siro a écrit :
02 juil. 2018 10:33
@Hibiscus : t'es sûr que c'est au programme de MPSI (ou même de prépa), la décidabilité ? Moi pas...
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.

Messages : 0

Inscription : 08 juin 2016 21:39

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par Zetary » 02 juil. 2018 13:37

Ou plutôt un aperçu de logique intuitionniste…

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par siro » 02 juil. 2018 14:10

Pas besoin de logique intuitionniste pour parler de décidabilité (et vice-versa).
Simon Billouet a écrit :
02 juil. 2018 13:33
siro a écrit :
02 juil. 2018 10:33
@Hibiscus : t'es sûr que c'est au programme de MPSI (ou même de prépa), la décidabilité ? Moi pas...
Non non, ce n'est pas même au programme de l'option informatique. C'est une tentative d'humour, je dirais. :)
La vache, il est abyssal cet humour... (et si c'est moi qui dit ça faut s'inquiéter)
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 0

Inscription : 19 avr. 2015 00:08

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par darklol » 05 juil. 2018 18:42

Dattier a écrit :
05 juil. 2018 18:01
Bonjour,

énoncé 152 : le miracle algébrique ?
Existe-t-il $ f $ une fonction réel, continue nul part, tel que $\forall x\in\mathbb R, f(x)\in\mathbb N[x]$ ?

Bonne journée.
La fonction indicatrice de $ \mathbb{Q} $ (ni miraculeuse, ni algébrique).
ENS Lyon
Ingénieur de recherche

Messages : 0

Inscription : 19 avr. 2015 00:08

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par darklol » 05 juil. 2018 19:06

SPOILER:
$ f(x) = x + 1 $ si $ x $ rationnel, $ f(x) = x - 1 $ si $ x $ irrationnel
ENS Lyon
Ingénieur de recherche

Messages : 0

Inscription : 19 avr. 2015 00:08

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par darklol » 06 juil. 2018 00:12

Ah oui en effet, remplace par $ x-1 $ par $ x+2 $ alors :)
ENS Lyon
Ingénieur de recherche

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par siro » 06 juil. 2018 10:01

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.

Messages : 0

Inscription : 20 mai 2018 16:59

Profil de l'utilisateur : Élève de lycée

Re: Les dattes à Dattier

Message par Zrun » 06 juil. 2018 13:10

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

Verrouillé