{% extends "articles/complexite-et-machine-de-turing/_layout.html" %} {% import "articles/complexite-et-machine-de-turing/_decklist.html" as decklist with context %} {% block section %} {% trans trimmed infest=card("Infest"), rotlung_reanimator=card("Rotlung Reanimator"), xathrid_necromancer=card("Xathrid Necromancer"), ancient_tomb=card("Ancient Tomb"), lotus_petal=card("Lotus Petal"), grim_monolith=card("Grim Monolith"), power_artifact=card("Power Artifact"), staff_of_domination=card("Staff of Domination"), gemstone_array=card("Gemstone Array"), djinn_illuminatus=card("Djinn Illuminatus"), reito_lantern=card("Reito Lantern"), memnarch=card("Memnarch"), stolen_identity=card("Stolen Identity"), donate=card("Donate"), artificial_evolution=card("Artificial Evolution"), glamerdye=card("Glamerdye"), prismatic_lace=card("Prismatic Lace"), fathom_feeder=card("Fathom Feeder"), karn_liberated=card("Karn Liberated"), capsize=card("Capsize"), decklist=decklist.deck(), cloak_of_invisibility=card("Cloak of Invisibility"), shared_triumph=card("Shared Triumph"), fungus_sliver=card("Fungus Sliver"), steely_resolve=card("Steely Resolve"), dread_of_night=card("Dread of Night"), wild_evocation=card("Wild Evocation"), recycle=card("Recycle"), privileged_position=card("Privileged Position"), blazing_archon=card("Blazing Archon"), vigor=card("Vigor"), wheel_of_sun_and_moon=card("Wheel of Sun and Moon"), mesmeric_orb=card("Mesmeric Orb"), prismatic_omen=card("Prismatic Omen"), choke=card("Choke"), olivia_voldaren=card("Olivia Voldaren"), cleansing_beam=card("Cleansing Beam"), coalition_victory=card("Coalition Victory"), soul_snuffers=card("Soul Snuffers"), illusory_gains=card("Illusory Gains"), incarnation=card("Incarnation") %}
Assez tourné autour du pot, il est temps de vous dire ce qu'est exactement une machine de Turing.
En théorie une machine de Turing est composée de quatre choses :
A première vu cette machine n'a pas l'air de faire grand chose en comparaison de nos ordinateurs. En gros elle écrit des caractères sur un ruban en se déplaçant le long de ce ruban. Au cours de ce programme elle peut potentiellement changer d'état et finalement lorsqu'elle se trouve dans une position pour laquelle elle n'a plus d'instruction elle s'arrête. En réalité, une machine de Turing a une puissance de calcul équivalente à celui de la plupart des langages de programmation tel que le C ou le Java. Oui, rien que ça !
Comment faire pour représenter un ruban avec des cartes Magic ?
L'idée sera d'utiliser des créatures sur le champ de bataille à la place des cases. La case sous la tête de lecture sera matérialisés par un jeton 2/2. Les cases situées immédiatement à gauche et à droite seront matérialisées par des jetons 3/3, puis les cases suivantes par des jetons 4/4 et ainsi de suites. Pour bien différencier les cases situées à gauche de la tête de lecture des cases situées à droite de la tête de lecture on considérera que les cases à droite correspondront à des jetons de couleur verte et que les cases à gauche correspondront à des jetons de couleur blanche. Quant à la 2/2 correspondant à la case sous la tête de lecture on a à priori pas de contrainte pour sa couleur.
Comment faire pour avoir des caractères dans les cases du ruban ?
Pour cela il faudrait pouvoir donner à chaque jeton une caractéristique que l'on associerait à un caractère. L'idée va être de se servir des types de créatures. Il en existe à Magic largement assez pour pouvoir associer à chaque caractère un type de créature. J'en profite pour faire remarquer que la tête de lecture peut changer le caractère de la case qu'elle lit, cela signifie qu'il va falloir trouver un effet qui va affecter uniquement le jeton 2/2 et pas les autres jetons. Lancer un sort tel que {{ infest }} semble le moyen idéal. La mort du jeton 2/2 pourrait alors déclencher un trigger créant un nouveau jeton 2/2 d'un autre type ce qui correspondrait exactement au fait de réécrire un caractère sous la tête de lecture. Pour cela pas de soucis il suffit d'utiliser au choix {{ rotlung_reanimator }} ou {{ xathrid_necromancer }} pour lesquels on aurait modifié les types de créatures et couleurs présents dans leur texte.
Comment décaler le ruban vers la droite ou la gauche ?
Pour décaler le ruban vers la droite, il suffit d'ajouter un marqueur +1/+1 à toutes les créatures blanches et de mettre un marqueur -1/-1 à toutes les créatures vertes et inversement pour décaler le ruban vers la gauche.
On comprend très vite que pour que cette méthode puisse marcher il faut que le jeton 2/ 2 soit vert lorsque l'on souhaite décaler le ruban vers la droite et qu'il soit blanc lorsqu'on veut décaler le ruban vers la gauche. En réalité le problème doit être pris à l'envers en considérant que la couleur du jeton 2/2 va définir la direction du décalage.
Bon tout ce qu'on a fait là n'est que théorique et il faut maintenant arriver à construire cela dans une vraie partie de Magic et mettre les joueurs dans une situation où ils seront forcés d’exécuter le programme de notre choix. En fait toutes toutes les cartes dont on va avoir besoin pour mettre en place cette situation seront dans le deck du premier joueur la bien nommée Alice et celle-ci va créer notre machine de Turing au premier tour à condition qu'elle ait une main de départ parfaite. Et pour arriver à ça on va avoir besoin d'utiliser seulement 42 cartes différentes sur les 20 000 existantes. Voici la decklist d'Alice :
{{ decklist }}C'est parti !
Alice joue {{ ancient_tomb }} et trois {{ lotus_petal }}s afin de jouer {{ grim_monolith }} et {{ power_artifact }} afin de générer une quantité arbitrairement grande de mana incolore. Puis {{ staff_of_domination }} permet de piocher la totalité du deck et {{ gemstone_array }} fournit le mana coloré nécessaire pour jouer tous les sorts.
A partir de là on a quelques cartes qui vont aider à la mise en place des choses :
Grâce à {{ donate }} on va donner à Bob un certain nombre de permanents : 31 {{ rotlung_reanimator }} et 7 {{ xathrid_necromancer }} dont les textes (types et couleurs) ont tous été soigneusement modifiés pour créer la table d'action de notre machine de Turing. En effet comme dit précédemment, on souhaite que lorsqu'un jeton 2/2 d'un certain type meurt, un jeton d'un autre type particulier soit créé et qu'il ait la couleur de notre choix. Tout ceci peut en effet être soigneusement préparé en amont grâce à {{ artificial_evolution }} et {{ glamerdye }}. Et qu'en est-il des jetons qui vont former la bande infinie de notre machine ? Et bien ces jetons sont créés à l'aide de {{ riptide_replicator }} et {{ capsize }}. Ainsi donc la table des actions ainsi que le ruban sont maintenant sous le contrôle de Bob, mais on ne va pas s'arrêter là. A côté de cette partie technique donc, on donne à Bob 5 autres permanents : {{ wild_evocation }}, {{ recycle }}, {{ privileged_position }}, {{ blazing_archon }}, {{ vigor }}. Bob va ainsi se retrouver dans une situation un peu délicate. Il n'a aucune carte en main ou en bibliothèque mais ne meurt pas à la pioche parce qu'il contrôle {{ recycle }}. Il n'a pas non plus de mana ou de capacité à activer. Enfin il ne pourra pas non plus attaquer Alice avec ses créatures car celle-ci possède aussi comme on va le voir un {{ blazing_archon }}. En définitive Bob va donc demeurer simple spectateur pour le reste de la partie.
Du côté d'Alice il y a aussi une mise en place particulière et complexe comportant :
A côté de ça, Alice contrôle aussi quelques permanents auxquels on va s'intéresser : {{ wheel_of_sun_and_moon }} l'enchantant, {{ vigor }}, {{ mesmeric_orb }}, {{ ancient_tomb }}, {{ prismatic_omen }}, {{ choke }} et bien entendu {{ blazing_archon }}.
En plus de ça Alice aura pris soin de cibler toutes les créatures avec {{ olivia_voldaren }} pour leur mettre un marqueur +1/+1 et leur donner un type commun.
Enfin pour que la mise en place soit complète il faut que la bibliothèque d'Alice contienne dans cet ordre : {{ cleansing_beam }}, {{ coalition_victory }}, {{ soul_snuffers }}, placés ainsi grâce à {{ reito_lantern }} et seul doit rester dans sa main {{ infest }}. Tous les autres permanents ayant été exilés à l'aide de {{ karn_liberated }} et {{ capsize }} (Karn pouvant exiler aussi Capsize et lui même).
Bien ! Regardons ce qu'il se passe maintenant du côté d'Alice.
Tour 1 :
Au début de son entretien, Alice lance {{ infest }}. Elle va en réalité tuer ainsi l'unique jeton 2/2 contrôlé par Bob. Ce dernier suivant son type de créature va déclencher la capacité d'un {{ rotlung_reanimator }} ou d'un {{ xathrid_necromancer }} spécifique qui va créer un nouveau jeton d'une couleur (soit vert soit blanc), d'un type spécifique, soit dégagé, soit engagé. Ce jeton nouvellement créé va alors se retrouver enchanté par {{ illusory_gains }} et arriver sous le contrôle d'Alice. Vous l'aurez compris ce jeton donc sous le contrôle d'Alice correspond au jeton sous la tête de lecture.
Je rappelle au passage que {{ infest }} n'a tué aucun {{ rotlung_reanimator }} ou {{ xathrid_necromancer }} car ces derniers ont un marqueur +1/+1 sur eux grâce à {{ olivia_voldaren }}.
Enfin lors de sa phase de pioche Alice va piocher {{ cleansing_beam }}.
Tour 2 :
A la phase de dégagement d'Alice le jeton enchanté par {{ illusory_gains }} va se dégager s'il était engagé et se faisant va meuler Alice d'une carte à cause de {{ mesmeric_orb }}, et donc {{ coalition_victory }} va se retrouver en dessous de la bibliothèque. On reviendra sur les conséquences de ce trigger plus tard lorsqu'il a lieu.
Alice doit lancer maintenant {{ cleansing_beam }} et doit donc choisir une cible. Seulement grâce à {{ olivia_voldaren }}, toutes les créatures du champ de bataille partagent un même type de créature et ce type est justement celui que l'on a donné à {{ steely_resolve }} pour que ces créatures aient le linceul. Les créatures de Bob quand à elles ne peuvent pas être ciblées car il contrôle {{ privileged_position }}. Cela ne laisse qu'une seule cible valide pour Alice : le jeton enchantée par {{ illusory_gains }} qui vient d'arriver sous son contrôle. Comme dit précédemment, ce jeton est soit vert soit blanc. Comme Alice et Bob possèdent tous deux {{ vigor }} à la résolution de {{ cleansing_beam }}, ils vont placer deux marqueurs +1/+1 sur toutes les créatures qu'ils contrôlent qui sont de la même couleur que ce jeton.
Lors de sa phase de pioche, Alice pioche {{ coalition_victory }} si la carte n'a pas été mise en dessous de sa bibliothèque, et dans le cas contraire elle pioche {{ soul_snuffers }}
Tour 3 :
Mais qu'en est-il de la fin de partie ? Et bien parmi tous les caractères encodés par notre machine de Turing il y a un symbole en particulier qui correspond à un symbole d'arrêt. Ce type de créature lorsqu'il est mis dans un cimetière crée un jeton particulier dégagé de couleur bleu chez Alice. Or Alice possède grâce à {{ prismatic_lace }} déjà des permanents rouges, verts, noirs et blancs mais aucun bleu ! Aussi grâce à {{ prismatic_omen }} Alice possède aussi un terrain de chaque type. Ainsi lorsqu'elle lancera {{ coalition_victory }} elle gagnera la partie. Si en revanche ce programme ne s'arrête pas alors selon les règles de Magic la partie se termine par un Match nul. Ainsi l'issu de la partie dépend uniquement de la faculté qu'à un certain programme à s'arrêter.
J'ai en définitive volontairement passé sous silence certaines parties techniques (oui, oui...) de cette démonstration mathématique pas comme les autres et pour tout ceux qui souhaiteraient lire la publication originale, je vous renvoie vers les liens externes situés à la fin de cet article. J'espère néanmoins vous avoir donné une bonne idée de ce qui a été démontré et comment cela a été démontré.
{% endtrans %} {% endblock %}