Oracle
Bonjour,
Peut on faire une série de questions oui-non à un oracle pour savoir si il dit la vérité sachant que soit il dit la vérité tout le temps soit il ment tout le temps.
Merci d’avance
Peut on faire une série de questions oui-non à un oracle pour savoir si il dit la vérité sachant que soit il dit la vérité tout le temps soit il ment tout le temps.
Merci d’avance
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
pardon, j'ai déjà posé la question : qu'est-ce qu'un oracle en mathématiques ?
S
Par exemple, soit $x$ une fonction de $\omega$ dans $\omega$, non récursive (sinon ça n'a pas d'intérêt).
Si $f$ est une autre fonction non récursive de $\omega$ dans $\omega$, dire que $f$ est récursive en $x$ est équivalent (modulo la thèse de Church) à dire que tu disposes d'un algorithme qui te permet de calculer $f(n)$ pour tout entier $n$, à condition de disposer d'un oracle que tu peux interroger quand tu veux pour lui demander la valeur de $x(k)$ pour un certain entier $k$.
On se sert beaucoup des oracles dans l'étude des problèmes NP-complets, par exemple.
.
S
Sauriez vous donner une suite de questions oui non qui mènerai à une démonstration?
Merci d’avance
@superpower : la réponse de @JLT ne te convient-elle pas ?
Question 1 : est-ce que $1=1$ ?
Si l'oracle ment, il répond NON.
Si l'oracle dit la vérité, il répond OUI.
Et ces deux réponses sont distinctes : tu peux donc savoir ce que tu cherches, non ? Ou alors tu n'as pas bien exposé le problème.
A ma dernière question je demandais pour une démonstration quelconque par exemple l’hypothèse de Riemann
Merci d’avance
Ainsi, par déduction tu sauras si elle est vraie ou pas.
Quant à la démonstration (dans un cas comme dans l'autre), c'est une autre histoire...
Est-ce que la première lettre de $D$ est $a_1$ ?
Est-ce que la première lettre de $D$ est $a_2$ ?
(...)
Est-ce que la première lettre de $D$ est $a_p$ ?
Est-ce que la deuxième lettre de $D$ est $a_1$ ?
Est-ce que la deuxième lettre de $D$ est $a_2$ ?
(...)
Est-ce que la deuxième lettre de $D$ est $a_p$ ?
etc.