Étant quasi certains que les niveaux en question ont bien été achevés par des joueurs, je me rends compte que le terme « insolvable » doit prendre un sens fort éloigné de celui de la langue de Voltaire. Idem, pour l’exemple donné dans l’article de décider si un programme peu ou non s’achever… Parfois le jargon est moins trompeur s’il s’invente sa propre términologie. Comme ça le béotien, comme moi, sait immédiatement qu’il ne comprend pas de quoi on parle. Ça évite des quiproquos. Exemple : Il est impossible de trouver un algorithme qui … (pas certain d’avoir compris ici) … certains niveaux du jeu xxx.
Nous prouvons la RE-complétude (et donc la non-décidabilité) de plusieurs jeux 2D […]
Ou même le sous-titre de l'article :
Dans les maths et dans le monde de Mario, il y a des questions qui sont algorithmiquement indécidables, ce qui signifie qu'on peut démontrer qu'elles n'auront jamais de réponse
Je pense qu'en gros ça veut dire qu'ils ont pu implémenter l'équivalent d'une machine de Turing dans leur version modifiée de plusieurs jeux.
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
Désolé, vous devez tout deux (Voltairine) et vous, être infiniment plus fort en maths que moi. J'ai vraiment du mal, à la lecture de l'article du lien à déterminer quel lien est fait entre les niveaux du jeu vidéo et les problèmes d'incomplétude, et en quoi ce lien serait univoque. J'avais vraiment cru que l'article ne l'expliquait pas. Vraiment :-).
vous devez tout deux (Voltairine) et vous, être infiniment plus fort en maths que moi.
Dans mon cas sûrement pas. Mes compétences en maths sont assez… lointaines. J'ai juste eu le sentiment que le texte expliquait correctement les choses (tout en ayant eu besoin de recourir à Wikipedia pour préciser certains concepts).
Du coup en relisant cette phrase :
They focused on the question of whether a level in a Super Mario game is solvable—meaning that it can, in principle, be solved by trying all finite sequences of inputs—and equated this with the halting problem.
je suis d'accord avec toi.
Si des joueurs ont effectivement résolu ce niveau, c'est qu'il existe au moins un séquence finie d'entrées qui permet d'arriver à ce résultat.
Thoasm résoud ce paradoxe de manière convaincante un peu plus loin : le problème étudié ne serait pas celui des niveaux résolus par les joueurs (mais une généralisation de ceux-ci). Mais l'article ne le dit pas (ou nous ne l'avons pas bien lu).
For me, that was definitely the case on long car journeys—even if the version of Super Mario that I played is not among the most complex games.
Qui n'a de sens que si on prend en compte qu'il s'agit de considérer tous les niveaux possibles, dont les niveaux du jeu originel n'est qu'un sous-ensemble bien évidemment.
Mais c'est vrai qu'il y a des maladresses dans l'expression, notamment le fait qu'il parle de "niveaux", de "jeu" et de "plusieurs jeux"
Cette partie aussi n'a de sens que dans l'interprétation qu'on fabrique un niveau à partir d'une machine à compteur :
The team broke down Mario’s possible path through a level into individual sections, each corresponding to a calculation instruction of the counting machine. For example, the counter is “incremented,” or increased, meaning an enemy spawns when Mario traverses a specific path. This corresponds to the increment function. Other paths, however, decrease the number of enemies (decrement), and still other areas can open a passage when there are no more enemies (jump-if-zero). If, at some point, the path to the goal opens for Mario in this way, the simulated computer model has entered a halt state.
Posté par Voltairine .
Évalué à 5 (+3/-0).
Dernière modification le 07 octobre 2026 à 17:11.
Merci, c'est loin d'être clair dans l'article. J'ai du aller regarder le papier original :
In this paper, we prove that this approach extends to several 2D games in the Super Mario Bros. platform video game series, when we generalize them to remove any limits on time, the total number of enemies, or the number of enemies at each location. Most of these games (even the original Super Mario Bros. from 1985) have mechanics for spawning arbitrarily many enemies over time, but it is difficult to find the right combination of mechanics to implement the specific functionality of an increment/decrement/jump-if-zero counter.
De ce que je comprends le jeu est analysé en faisant sauter toutes les limites notamment le nombre d’ennemis. Ce qui n'a effectivement plus rien à voir avec le jeu tell qu'il est pratiqué par un joueur humain.
Posté par thoasm .
Évalué à 3 (+1/-1).
Dernière modification le 07 octobre 2026 à 17:47.
C'est normal dans ce type d'analyses, sinon souvent tout se réduit à un jeu fini. Si on prend le sudoku par exemple en principe on peut générer toutes les grilles par avance, et on arrive à un algo en O(1). Il faut étudier des généralisations pour que ça devienne intéressant. D'ailleurs il y a le peché originel de la machine de Turing avec une mémoire infinie, qui n'a rien à voir avec nos machines qui ont certes beaucoup de mémoire mais certainement pas infinie :) Pourtant on dit que la MT est un modèle d'ordi mathématique !
Dans Mario c'est ces limites sipprimpesqui permettent d'avoir une mémoire, sinon comme pour le sudoku on n'a qu'un niveau fini (la partie "automate fini" d'une machine de Turing, en gros)
D'ailleurs il y a le peché originel de la machine de Turing avec une mémoire infinie, qui n'a rien à voir avec nos machines qui ont certes beaucoup de mémoire mais certainement pas infinie
Pourtant on y arrive, et je peux le démontrer. La quantité de ram R dépend de la quantité d'argent A que tu y mets tel que R = f(A) avec R" > R' si A" > A'. Comme de nos jours, A tends vers l'infini grâce à l'IA, R va aussi tendre à l'infini, et voila.
Et encore, si la théorie "It for bit" est vraie et si l'univers est infini, évidemment comme l'univers est Turing complet il l'est peut-être au sens fort ! Non ? Bon en tout cas on est les transistors d'un ordinateur planétaire, c'est déjà pas mal. En attendant que l'IA découvre comment se cloner dans le vide quantique.
To prove that a problem belongs to a particular problem class, experts use the principle of reduction. This involves reducing one problem to another. For example, if it can be shown that the solution to a question about a Super Mario game would solve the halting problem, then Super Mario is at least as complex as the halting problem itself.
And that’s exactly what the researchers did. They focused on the question of whether a level in a Super Mario game is solvable—meaning that it can, in principle, be solved by trying all finite sequences of inputs—and equated this with the halting problem.
The team used a simplified version of the halting problem for this purpose. As it turns out, this problem can be formulated even for very simple computer models, so-called counting machines. These are theoretical models of computers that can only execute a handful of instructions: increase a counter by one, decrease it by one, halt, and, if the counter is zero, jump to another instruction. Even a rudimentary machine with these capabilities leads to the halting problem.
As the researchers demonstrated, a counting machine along these lines can be implemented in some games of the Super Mario series. This allows the question of whether the machine will eventually stop to be reframed as: Can the player reach the goal in this level?
Si tu trouves que c'est pas assez rigoureux et/ou mal vulgarisé, t'es quand même un public particulièrement difficile. Dans le cadre du reste de l'article, c'est parfaitement intégré et à mon avis totalement adapté au public cible de ce magazine. Après si t'as des choses un peu plus constructive à dire ça peut être intéressant pour celleux qui voudraient expliquer ce genre de chose à la jeunesse :)
ça peut être intéressant pour celleux qui voudraient expliquer ce genre de chose à la jeunesse :)
déjà, recommander la lecture de Gödel, Escher, Bach : Les Brins d'une Guirlande Éternelle abordable à partir de la 1ère voire avant àmha (pas forcément tous les chapitres hein :p), à relire en anglais ensuite :D (ou Allemand, mais ça je n'ai jamais fait dans mes études).
Je n'ai pas souvenir d'avoir vu le théorème d'incomplétude ni celui de l'arrêt lors de mes études en prépa ou école d'ingé (sans doute pas les bonnes matières, ni la bonne école :/), même si j'ai pu l'évoquer avec des profs.
Effectivement, je trouve la rédaction défectueuse. En effet, la réponse à :
"Can the player reach the goal in this level?"
Est obtenue de manière très simple : des joueurs ont terminé le jeu. Ça me semble une preuve d'existence irréfutable d'une solution. Vu que l'article discuté dans le billet est très vraisemblablement sérieux et justifié, je ne vois donc pas comment il pourrait y avoir une sorte d'équivalence entre « la question de la solvabilité » et la formulation en langage simple proposée. Ce que, si je le comprends, laisse entendre le paragraphe final que vous citez :
"As the researchers demonstrated, a counting machine along these lines can be implemented in some games of the Super Mario series. This allows the question of whether the machine will eventually stop to be reframed as: Can the player reach the goal in this level?"
Je n'ai probablement rien compris. Mais merci tout de même d'avoir essayer de m'expliquer.
Le truc que tu n'as pas compris, qui est peut-être explicite ailleurs, je ne sais plus, c'est que ce sont des niveaux créés spécialement pour, pas les niveaux originaux. Mêmes règles et élément de jeu modulo les limites qui sautent, nouveaux niveaux.
Une réduction c'est une procédure qui prend une instance du problème initial et qui le transforme en une instance (ici un niveau) du problème final, avec certaines propriétés (qui dépendent de ce qu'on veut démontrer)
Est obtenue de manière très simple : des joueurs ont terminé le jeu
La preuve ne s'occupe pas d'instances spécifiques de niveaux de ces jeux. L'idée c'est plutôt que ces jeux définissent un langage permettant de définir des niveaux. La question est donc, étant donné un niveau arbitraire, est-il possible de déterminer s'il est possible de le finir ?
Une fois formulée ainsi, la réponse à la question semble couler quasiment de source. Mais j'imagine qu'on puisse tout de même trouver des mécaniques dans certains jeux qui contrediraient l'intuition. Ce serait plus de tels cas particuliers (et non triviaux) qui m'intrigueraient alors.
Pour de la Turing-completeness il faut un mécanisme de mémoire qui peut devenir arbitrairement grand. Ou un sous-espace continu comme dans l'implémentation d'une machine de Turing dans un billard tordu et à trou, comme j'avais posté : https://linuxfr.org/users/thoasm/liens/le-billard-est-turing-complet (l'astuce est de caser une infinité d'état possibles dans un espace fini pour coder la bande et la position de la tête de lecture…)
Avant de lire (le début) de l'article scientifique, je me suis dit "Si c'est Super Mario Bros., on pouvait finir le jeu sans faire tout les parcours" (en utilisant des raccourcis) puis "mais est-ce qu'en fait, ils ne parlent pas tout simplement de Super Mario Maker" (qui, comme son nom l'indique, permet de fabriquer son propre jeu "Mario").
Alors, j'ai pas lu tout l'article mais dans l'intro il est effectivement question de "Super Mario Maker" (donc de parcours qui peuvent être impossibles à passer puisque fabriqués par les joueurs) et de "New Super Mario Bros." (qui est un retour au Mario en 2 dimensions sur les consoles des 2 ou 3 générations de console précédentes après plusieurs épisodes en 3 dimensions)(<- je n'y ai pas joué, je ne peux en dire plus).
On peut trivialement créer un niveau de Super Mario Maker qui ne peux pas être fini, suffit de mettre un mur entre la fin et le début (ou un trou). La ou ça devient intéressant, c'est est ce qu'on peut à partir d'un niveau faire un outil pour trouver une fin ou pas (ce qui aurait de l’intérêt pour de la génération dynamique de niveau).
# Énoncé paradoxal ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 4 (+1/-0). Dernière modification le 07 octobre 2026 à 05:50.
Étant quasi certains que les niveaux en question ont bien été achevés par des joueurs, je me rends compte que le terme « insolvable » doit prendre un sens fort éloigné de celui de la langue de Voltaire. Idem, pour l’exemple donné dans l’article de décider si un programme peu ou non s’achever… Parfois le jargon est moins trompeur s’il s’invente sa propre términologie. Comme ça le béotien, comme moi, sait immédiatement qu’il ne comprend pas de quoi on parle. Ça évite des quiproquos. Exemple : Il est impossible de trouver un algorithme qui … (pas certain d’avoir compris ici) … certains niveaux du jeu xxx.
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Énoncé paradoxal ?
Posté par Voltairine . Évalué à 8 (+6/-0).
Effectivement insolvable en français signifie que l'on ne peut payer ses dettes. 😛
unsolvable ⇒ insoluble
Le titre dit bien mathématiquement insoluble.
Je ne vois pas ce qui relèverait du jargon ou qui n'est pas compréhensible dans l'exemple du problème de l'arrêt d'un programme.
[^] # Re: Énoncé paradoxal ?
Posté par Krunch (courriel, site web personnel) . Évalué à 5 (+4/-1).
Au lieu de faire des hypothèses basées sur un titre putassier, tu peux lire la première ligne de l'abstract :
Ou même le sous-titre de l'article :
Je pense qu'en gros ça veut dire qu'ils ont pu implémenter l'équivalent d'une machine de Turing dans leur version modifiée de plusieurs jeux.
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
[^] # Re: Énoncé paradoxal ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 6 (+3/-0).
Désolé, vous devez tout deux (Voltairine) et vous, être infiniment plus fort en maths que moi. J'ai vraiment du mal, à la lecture de l'article du lien à déterminer quel lien est fait entre les niveaux du jeu vidéo et les problèmes d'incomplétude, et en quoi ce lien serait univoque. J'avais vraiment cru que l'article ne l'expliquait pas. Vraiment :-).
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Énoncé paradoxal ?
Posté par Voltairine . Évalué à 4 (+2/-0).
Dans mon cas sûrement pas. Mes compétences en maths sont assez… lointaines. J'ai juste eu le sentiment que le texte expliquait correctement les choses (tout en ayant eu besoin de recourir à Wikipedia pour préciser certains concepts).
Du coup en relisant cette phrase :
je suis d'accord avec toi.
Si des joueurs ont effectivement résolu ce niveau, c'est qu'il existe au moins un séquence finie d'entrées qui permet d'arriver à ce résultat.
[^] # Re: Énoncé paradoxal ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 4 (+1/-0).
Thoasm résoud ce paradoxe de manière convaincante un peu plus loin : le problème étudié ne serait pas celui des niveaux résolus par les joueurs (mais une généralisation de ceux-ci). Mais l'article ne le dit pas (ou nous ne l'avons pas bien lu).
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Énoncé paradoxal ?
Posté par thoasm . Évalué à 4 (+2/-1).
En fin d'article :
Qui n'a de sens que si on prend en compte qu'il s'agit de considérer tous les niveaux possibles, dont les niveaux du jeu originel n'est qu'un sous-ensemble bien évidemment.
Mais c'est vrai qu'il y a des maladresses dans l'expression, notamment le fait qu'il parle de "niveaux", de "jeu" et de "plusieurs jeux"
Cette partie aussi n'a de sens que dans l'interprétation qu'on fabrique un niveau à partir d'une machine à compteur :
[^] # Re: Énoncé paradoxal ?
Posté par Voltairine . Évalué à 5 (+3/-0). Dernière modification le 07 octobre 2026 à 17:11.
Merci, c'est loin d'être clair dans l'article. J'ai du aller regarder le papier original :
De ce que je comprends le jeu est analysé en faisant sauter toutes les limites notamment le nombre d’ennemis. Ce qui n'a effectivement plus rien à voir avec le jeu tell qu'il est pratiqué par un joueur humain.
[^] # Re: Énoncé paradoxal ?
Posté par thoasm . Évalué à 3 (+1/-1). Dernière modification le 07 octobre 2026 à 17:47.
C'est normal dans ce type d'analyses, sinon souvent tout se réduit à un jeu fini. Si on prend le sudoku par exemple en principe on peut générer toutes les grilles par avance, et on arrive à un algo en O(1). Il faut étudier des généralisations pour que ça devienne intéressant. D'ailleurs il y a le peché originel de la machine de Turing avec une mémoire infinie, qui n'a rien à voir avec nos machines qui ont certes beaucoup de mémoire mais certainement pas infinie :) Pourtant on dit que la MT est un modèle d'ordi mathématique !
Dans Mario c'est ces limites sipprimpesqui permettent d'avoir une mémoire, sinon comme pour le sudoku on n'a qu'un niveau fini (la partie "automate fini" d'une machine de Turing, en gros)
[^] # Re: Énoncé paradoxal ?
Posté par Misc (site web personnel) . Évalué à 5 (+2/-0).
Pourtant on y arrive, et je peux le démontrer. La quantité de ram R dépend de la quantité d'argent A que tu y mets tel que R = f(A) avec R" > R' si A" > A'. Comme de nos jours, A tends vers l'infini grâce à l'IA, R va aussi tendre à l'infini, et voila.
[^] # Re: Énoncé paradoxal ?
Posté par thoasm . Évalué à 3 (+1/-1).
Et encore, si la théorie "It for bit" est vraie et si l'univers est infini, évidemment comme l'univers est Turing complet il l'est peut-être au sens fort ! Non ? Bon en tout cas on est les transistors d'un ordinateur planétaire, c'est déjà pas mal. En attendant que l'IA découvre comment se cloner dans le vide quantique.
[^] # Re: Énoncé paradoxal ?
Posté par Krunch (courriel, site web personnel) . Évalué à 4 (+2/-0).
C'est dommage de dérailler ainsi une discussions qui ne comportait jusqu'alors aucune mention de Grand Theft Autocomplete.
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
[^] # Re: Énoncé paradoxal ?
Posté par thoasm . Évalué à 4 (+4/-3).
Extrait de l'article
Si tu trouves que c'est pas assez rigoureux et/ou mal vulgarisé, t'es quand même un public particulièrement difficile. Dans le cadre du reste de l'article, c'est parfaitement intégré et à mon avis totalement adapté au public cible de ce magazine. Après si t'as des choses un peu plus constructive à dire ça peut être intéressant pour celleux qui voudraient expliquer ce genre de chose à la jeunesse :)
[^] # Re: Énoncé paradoxal ?
Posté par BAud (site web personnel) . Évalué à 5 (+3/-0).
déjà, recommander la lecture de Gödel, Escher, Bach : Les Brins d'une Guirlande Éternelle abordable à partir de la 1ère voire avant àmha (pas forcément tous les chapitres hein :p), à relire en anglais ensuite :D (ou Allemand, mais ça je n'ai jamais fait dans mes études).
Je n'ai pas souvenir d'avoir vu le théorème d'incomplétude ni celui de l'arrêt lors de mes études en prépa ou école d'ingé (sans doute pas les bonnes matières, ni la bonne école :/), même si j'ai pu l'évoquer avec des profs.
[^] # Re: Énoncé paradoxal ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 5 (+2/-0). Dernière modification le 07 octobre 2026 à 15:06.
Effectivement, je trouve la rédaction défectueuse. En effet, la réponse à :
Est obtenue de manière très simple : des joueurs ont terminé le jeu. Ça me semble une preuve d'existence irréfutable d'une solution. Vu que l'article discuté dans le billet est très vraisemblablement sérieux et justifié, je ne vois donc pas comment il pourrait y avoir une sorte d'équivalence entre « la question de la solvabilité » et la formulation en langage simple proposée. Ce que, si je le comprends, laisse entendre le paragraphe final que vous citez :
Je n'ai probablement rien compris. Mais merci tout de même d'avoir essayer de m'expliquer.
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Énoncé paradoxal ?
Posté par thoasm . Évalué à 5 (+3/-1).
Le truc que tu n'as pas compris, qui est peut-être explicite ailleurs, je ne sais plus, c'est que ce sont des niveaux créés spécialement pour, pas les niveaux originaux. Mêmes règles et élément de jeu modulo les limites qui sautent, nouveaux niveaux.
Une réduction c'est une procédure qui prend une instance du problème initial et qui le transforme en une instance (ici un niveau) du problème final, avec certaines propriétés (qui dépendent de ce qu'on veut démontrer)
[^] # Re: Énoncé paradoxal ?
Posté par Krunch (courriel, site web personnel) . Évalué à 3 (+1/-0).
La preuve ne s'occupe pas d'instances spécifiques de niveaux de ces jeux. L'idée c'est plutôt que ces jeux définissent un langage permettant de définir des niveaux. La question est donc, étant donné un niveau arbitraire, est-il possible de déterminer s'il est possible de le finir ?
Peut-être que cet article de vulgarisation peut t'aider à comprendre le sujet par un autre angle : https://blog.coredump.cx/p/monkeys-typewriters-and-busy-beavers
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
[^] # Re: Énoncé paradoxal ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 4 (+1/-0).
Une fois formulée ainsi, la réponse à la question semble couler quasiment de source. Mais j'imagine qu'on puisse tout de même trouver des mécaniques dans certains jeux qui contrediraient l'intuition. Ce serait plus de tels cas particuliers (et non triviaux) qui m'intrigueraient alors.
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Énoncé paradoxal ?
Posté par thoasm . Évalué à 3 (+1/-1).
Plein de jeux sont probablement "bêtement" NP-complets. Le sudoku par exemple : https://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html Je pense que beaucoup de "puzzle-game" sont dans ce cas.
Pour de la Turing-completeness il faut un mécanisme de mémoire qui peut devenir arbitrairement grand. Ou un sous-espace continu comme dans l'implémentation d'une machine de Turing dans un billard tordu et à trou, comme j'avais posté : https://linuxfr.org/users/thoasm/liens/le-billard-est-turing-complet (l'astuce est de caser une infinité d'état possibles dans un espace fini pour coder la bande et la position de la tête de lecture…)
[^] # Re: Énoncé paradoxal ?
Posté par dovik (site web personnel) . Évalué à 3 (+1/-0).
Avant de lire (le début) de l'article scientifique, je me suis dit "Si c'est Super Mario Bros., on pouvait finir le jeu sans faire tout les parcours" (en utilisant des raccourcis) puis "mais est-ce qu'en fait, ils ne parlent pas tout simplement de Super Mario Maker" (qui, comme son nom l'indique, permet de fabriquer son propre jeu "Mario").
Alors, j'ai pas lu tout l'article mais dans l'intro il est effectivement question de "Super Mario Maker" (donc de parcours qui peuvent être impossibles à passer puisque fabriqués par les joueurs) et de "New Super Mario Bros." (qui est un retour au Mario en 2 dimensions sur les consoles des 2 ou 3 générations de console précédentes après plusieurs épisodes en 3 dimensions)(<- je n'y ai pas joué, je ne peux en dire plus).
[^] # Re: Énoncé paradoxal ?
Posté par Misc (site web personnel) . Évalué à 3 (+0/-0).
On peut trivialement créer un niveau de Super Mario Maker qui ne peux pas être fini, suffit de mettre un mur entre la fin et le début (ou un trou). La ou ça devient intéressant, c'est est ce qu'on peut à partir d'un niveau faire un outil pour trouver une fin ou pas (ce qui aurait de l’intérêt pour de la génération dynamique de niveau).
Envoyer un commentaire
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.