Comments on Vulgarisation sur la notion d'oracle en informatique théorique

Bonne introduction à quelques problématiques de l'informatique théorique !

Concernant l'énigme, si je ne dis pas de bêtise je crois que ceci fonctionne même si c'est probablement excessivement compliqué :

On dit que (i, j) <= (k, l) ssi (#{i,j},i,j) <= (#{k,l},k,l) (ordre lexicographique), où #{x,y} désigne le nombre de portes OK parmi {x,y}.

L'algorithme suivant appelle au plus quatre fois l'oracle :

Appel 1:

L = [(1, 2), (2, 3), (1, 3)]

1. L[0] est dans le top 2 de L pour l'ordre défini plus haut.
2. L[1] est dans le top 2 de L pour l'ordre défini plus haut.
3. L[2] est dans le top 2 de L pour l'ordre défini plus haut.

L'oracle me donne un (i,j) qui est dans le top 2, en particulier les portes i et j ne sont pas simultanément KO (ceci ne peut se produire que pour au plus une paire).

Appel 2:

1. La porte i est OK
2. La porte j est OK
3. La porte i est KO ou (exclusif) la porte j est KO

Si i et j sont toutes les deux OK, la phrase 3 est fausse et l'oracle doit répondre 1 ou 2 (gagné!).
Sinon, l'oracle peut répondre 3 (ou une et une seule des deux autres réponses, gagné aussi!).

Supposons que l'oracle réponde 3: i est KO ou (exclusif) j est KO.

On note (k,l,m) les portes autres que i et j et on recommence les deux étapes, ce qui nous fait gagner nous donne (au pire des cas) deux indices i',j' tels que i,j,i',j' sont deux à deux distincts et i' KO xor j' KO également.

L'indice restant dans {1, 2, 3, 4, 5} \ {i,j,i',j'} désigne une porte OK, gagné!

Il me semble que dans l'exemple de la réponse de Vicnent toutes les phrases sont fausses si l'on suppose que les portes 1 et 4 mènent à la mort ?
Le lutin doit donc l'exécuter ou quelque chose m'échappe.
En posant les questions de la façon suivante on est sur de ne pas énoncer plus d'une phrases fausses :

1 ou 2 ou les deux mènent à la mort
2 ou 3 ou 4 ou les trois mènent à la mort
3 ou 4 ou les deux mènent à la mort

GPT4 …

<je veux que tu te mettes dans la peau d'un logicien expert, très expérimenté. Voici un problème. Je veux que tu me donnes dans un premier temps la réponse puis que tu m'expliques ensuite ton raisonnement.
> + copié collé de ton problème.

Réponse : ---------------------------

Interrogez le lutin avec les questions suivantes :

La porte 1 mène à la mort et la porte 2 mène à la mort.
La porte 2 mène à la mort et la porte 3 mène à la mort.
La porte 3 mène à la mort et la porte 4 mène à la mort.
Si le lutin répond qu'une de ces phrases est vraie, cela signifie que les deux portes mentionnées dans cette phrase mènent à la mort. Ouvrez alors la cinquième porte.

Si le lutin ne confirme aucune de ces phrases, alors cela signifie que chaque phrase contient au moins une porte qui ne mène pas à la mort, car le lutin doit dire une vérité parmi les propositions. Vous pouvez alors ouvrir une des portes qui n'apparaît que dans une seule des phrases, sachant qu'elle ne mènera pas à la mort.

Raisonnement:

Contraindre les réponses du lutin: Vous ne pouvez poser que trois questions au lutin, et il doit répondre avec une seule vérité. Vous devez donc formuler vos questions de manière à ce qu'au moins une des phrases fournies au lutin contienne une porte qui mène sûrement au trésor.

Exclure les mauvaises portes: Les phrases posées au lutin sont construites de manière à ce que si le lutin dit qu'une des phrases est vraie, vous serez sûr que les deux portes mentionnées dans cette phrase sont mauvaises. Cela ne laissera qu'une seule porte, la cinquième, comme option sûre.

Assurer une option sûre: Si le lutin ne confirme aucune des phrases, cela signifie que chaque phrase contient au moins une porte qui ne mène pas à la mort. Vous pouvez alors ouvrir l'une des portes qui n'apparaît que dans une seule des phrases, sachant qu'elle ne mènera pas à la mort.

Minimisation du risque: Le lutin essaiera de donner la réponse la moins utile, mais en posant les questions de cette manière, vous vous assurez que la réponse du lutin sera toujours utile pour identifier une porte sûre.

En suivant cette stratégie, vous pouvez identifier à coup sûr une porte qui ne mène pas à la mort.

END REPONSE ---------------------------

Une variante qui pourrait rendre le problème du lutin plus intéressant (mais aussi peut-être plus dur à systématiser par rapport à l'approche proposée par jeanas est que parmi les trois phrases énoncées, *exactement une* doit être fausse, sous peine de mort.
Avec cette restriction j'ai une solution en au plus 3 interrogations, je pe demande si on peut faire mieux.

A : au plus une porte parmi 1 et 2 mène à la mort
B : au plus une porte parmi 2 et 3 mène à la mort
C : la porte 2 mène à la mort, et de même pour la porte 1 ou pour la porte 3

Si le lutin répond que C est vraie, on emprunte la porte 4 vers le trésor. Si il répond A (ou, mutatis mutandis, B), on propose les affirmations suivantes

A' : la porte 1 mène au trésor
B' : la porte 2 mène au trésor
C' : exactement une porte parmi 1 et 2 mène à la mort

Si il répond que A' ou B' est vraie, on a fini. Sinon, C' est vraie, donc exactement une porte parmi 3, 4 et 5 mène à la mort et on fait la 3ème étape suivante :

A'' : la porte 3 mène au trésor
B'' : la porte 4 mène au trésor
C'' : la porte 5 mène au trésor

That strategy for the lottery doesn't quite work as described, because when you only have two possibly values left, you can't exclude either of them. But jeanas has the right idea, you can ask questions until you reduce the winning numbers to just two possibly combinations, in which case you'll need to buy two tickets to win the jackpot; or if you're particularly stingy with lottery tickets, you can ask questions about both this Sunday and the next Sunday, and the oracle will have to reveal the winning combination for at least one of them.

On second thought, in the original stated version of the question, where the person that I ask isn't the cruel Doctor No who <URL: https://xkcd.com/246/ > stabs you if you ask tricky questions, but someone omniscient, I can do better.

Before asking anything about the doors, identify the lottery numbers that will be drawn this Sunday. Take all the numbers that may be drawn in the lottery, choose any three, for each three state that that number is not the lowest number that will be drawn in tomorrow's lottery, this way you eliminate one possible number as the lowest. Repeat by asking about three numbers that you haven't eliminated, this excluding another number, until you eventually eliminate all but one number and so you know that that one is the lowest number that will be drawn. Find the second lowest number in a similar way, then the third lowest etc. After you've found the lottery numbers, you can ask questions to find a safe door. Or, if you're more patient, you can ask questions to solve any other problem, such as find a proof of P ≠ NP or learn that there is no such proof. If you have access to such an oracle, you might even get tempted to never leave.

For every permutation (u, v, w, x, y) of the doors, I ask the cruel Doctor No about the following three statements: door u is safe; one of the doors v or w is safe; one of the doors x or y is safe. If the Doctor ever replies that a door is safe then I just enter that one. Otherwise there will be three doors, A, B, and C, such that the Doctor has told me that one of A or B is safe, he has told me that one of B or C is safe, and he has told me that one of A or C is safe. That implies that at most one of those three doors will kill me. Ask Doctor No about these three statements: door A is safe, door B is safe, door C is safe. Whichever he replies I can enter. As stated this is 11 questions, though if you are a bit more clever you'll find that 6 questions total is enough, because you can identify either a safe door or three doors of which two are safe in just 5 questions.

Dans des entrées précédentes sur les ordinaux vous sembliez indiquer qu'il existe une certaine équivalence entre nombre ordinal et classe de calculabilité, est-ce que ça a un rapport avec le degré de Turing ou ça n'a rien à voir ?

Pour l'énigme, il me semble qu'on peut juste fournir des triplets d'affirmations de la forme : (a) les deux portes mortelles ne sont pas m1 et n1, (b) les deux portes mortelles ne sont pas m2 et n2, (c) les deux portes mortelles ne sont pas m3 et n3. En prenant m1 ≠ n1, m2 ≠ n2, m3 ≠ n3, et {m1, n1}, {m2, n2}, {m3, n3} deux à deux distincts, on est bien sûr qu'au plus une des affirmations (a), (b), (c) est fausse, et quand le lutin nous donne une affirmation vraie, on peut éliminer l'un des « 2 parmi 5 » = 10 paires possibles, et recommencer itérativement avec trois paires non encore éliminées, jusqu'à ce qu'il n'y ait plus que deux paires (distinctes) possibles. À ce stade, ces deux paires couvrent 3 ou 4 éléments, et en prenant le cinquième, on gagne.

> si on remplace 5, 2, 3, 1 dans l'énigme par respectivement k, m, k′, m′ (avec 0<k<m et 0<k′<m′)

Goal False. Proof. lia. Qed.