Talk:StackFlow
Implementing StackFlow in Magic: the Gathering
The following attempted reduction from StackFlow to Magic: the Gathering is moved here from the article page because it has a bug we don't know how to fix.
User:Ais523 has made an attempt to construct a different proof that Magic: the Gathering is Turing-complete: it works by emulating The Waterfall Model using Hungry Lynx, Noxious Ghoul, and Rotlung Reanimator. We should describe that on the wiki later, but for now you can only find it in the freenode/#esoteric chat logs near 2018-03-01/--03-03. – b_jonas 19:03, 3 March 2018 (UTC)
In order to create an implementation of StackFlow using Magic cards, we need some way to represent stacks, and some way to represent rules, that compute according to the rules of the game. The computation is done entirely using triggered abilities, with no choices to be made by any player, and requires only two players. (It can be seen that StackFlow works in quite a similar way to triggered abilities in Magic already; everything happens as a consequence of stack elements being popped, including the popping of other stack elements.)
A method of representing stacks in Magic, due to Alex Churchill, already exists; a stack is represented using a creature for each stack element, with the creature's creature type representing the symbol, and the creature's toughness representing the distance from the head of the stack. (Toughnesses can go unboundedly high in Magic, meaning that we can track the order of an unlimited number of stack elements.) We use a toughness of 3 for the head of the stack, to prevent creatures dying incidentally as a side effect during other actions. All these stacks are controlled by the same player (and all the events take place on the other player's turn).
We use a different creature type for each symbol of each stack. Additionally, for each stack symbol, we use an additional creature type, which is given to all creatures in that stack. Our creatures are generated as tokens with only one creature type, but because which stack a creature belongs to is entirely defined by that creature type, we can grant the other creature type using copies of Dralnu's Crusade (with their text altered using Artificial Evolution in order to make them refer to different creature types), to create static "all Xs are Ys" effects. Dralnu's Crusade also has two other effects; the color-changing effect is irrelevant in this construction, but the +1 to power and toughness that it gives is relevant, and thus is cancelled out using Engineered Plague set to the same creature type. (In order to create the large number of enchantments with the same name required without running afoul of deck construction rules, the enchantments are temporarily enchanted using Opalescence, allowing token copies of them to be created using cards like Rite of Replication, which can be repeatedly salvaged from the graveyard and re-cast using cards like Elixir of Immortality; Opalescence can be destroyed again when we're done in order to make the enchantment creatures back into enchantments.)
For each of the creature types that represent stacks, there is a Noxious Ghoul which is altered using Artificial Evolution to look at that creature type, controlled by the active player (the opponent of the player who controls all the stacks), and protected from the effect of the other Noxious Ghouls via giving it all creature types using Blades of Velis Vel. The inactive player controls one copy of Cathars' Crusade. The combined effect is that whenever a creature enters the battlefield on one of the stacks, all creatures on the stacks will become tougher by 1 (due to the effect of Cathars' Crusade), and then all creatures on all other stacks will become less tough by 1 (due to the effect of Noxious Ghoul, which resolves later due to being controlled by the active player and Magic's tiebreak rules for simultaneous triggers.
For each stack, we add one further symbol, a "blank symbol", with a creature type to match. Unlike regular symbols, we put sufficiently many copies of Engineered Plague on the battlefield, set to that symbol's creature type, so that any 2/2 token creature of that type dies instantly upon being created. Creating a creature of the blank symbol type, therefore, will increase the toughness of all creatures in that stack without adding any new creatures to the stack. This effect can be used to adjust the toughness at which a stack starts, increasing it by 1.
We also need to be able to adjust the toughness at which a stack starts in the other direction (so as to be able to pop a stack via reducing it to 0). To do this, we use a creature type that is not used for any other purpose, and have a Noxious Ghoul set to that creature type (owned by the inactive player), together with two Engineered Plagues that are also set to that creature type. This means that creating a 2/2 creature token of that type under the active player's control will cause all creatures on the stacks to get -1/-1. In order to decrease the toughness at which a stack starts by 1, it suffices to increase the toughness at which all other stacks start by 1 (via pushing blank symbols onto them), then decreasing the toughness at which all stacks start by 1.
Finally, all that we need is a method of creating specific creatures, in a specific order, under specific controllers, whenever a creature of a specific type dies, noting that we only need a construction for the case where the creatures owned by the active player (which push symbols or blank symbols onto the stacks) are created before the creatures owned by the inactive player (which symmetrically pop all stacks). We achieve this using a series of Rotlung Reanimators (protected from Noxious Ghouls using Blades of Velis Vel):
- For the "push"/toughness increase rules, we have one Rotlung Reanimator controlled by each player; the copy controlled by the inactive player resolves first and creates the required token, while the copy controlled by the active player resolves second, and creates a creature of an otherwise unused type, which has sufficiently many copies of Engineered Plague pointed at it that it instantly dies, just like the blank symbols do. The death can be triggered on recursively, meaning that any number of "push" rules can run in response to a death, and in a specific order.
- For the "pop"/toughness reduce rules, we have a Rotlung Reanimator controlled by the active player; it creates a token of an otherwise unused type, and that type has a Dralnu's Crusade causing it to additionally be of the global-toughness-decreasing type, and sufficiently many Engineered Plagues set to that type that it has 0 toughness upon creation (and thus dies as soon as state-based actions are checked). However, the Reanimator does have to wait for state-based actions, whereas the Noxious Ghoul that looks at the global-toughness-decreasing type triggers as soon as the token is created, and thus the Reanimator's effect enters the stack second and so resolves first. The result is that we can chain any number of Rotlung Reanimator triggers (ending in the last rule of a sequence, for which the created token is of a type that no Rotlung Reanimator triggers on); the Noxious Ghoul triggers build up below them on the Magic stack, and then all resolve at the end of the ruleset.
Now all we need to do is to be able to encode rules as a sequence of triggered abilities. For each symbol of each stack, we arrange that when a creature of the type that represents that symbol dies, the following events happen in order:
- Two blank symbols are pushed onto that stack (because the head of stack will have toughness 1 after it is popped, and the head of a stack is supposed to have toughness 3, so we need to add two in order to get it to where it should be);
- For each symbol that that rule pushes onto a stack, a token of the corresponding creature type is created (a "push" rule);
- For each stack that is not popped by the rule, three blank symbols are pushed onto that stack;
- All creatures on the stacks have their toughness reduced by 3.
At first, it seems that this would require a great many creature types to trigger on. However, the last step is shared between all rules, and the penultimate step is shared between all rules on a stack. Thus, the total usage of creature types is:
- 1 per stack (the creature type common to all symbols on that stack);
- 1 per symbol (the creature type for that symbol);
- 1 (the global toughness decreasing symbol);
- 1 per symbol (the second of the two pushes that occur when that symbol is popped; the first does not need a creature type of its own because it triggers on the symbol itself);
- 1 per "push" rule (the push that that rule causes);
- 3 times (the number of stacks minus 1) per stack (the blank symbol pushes);
- 3 (the triggers for the global toughness reductions).
Given t stacks, y symbols, r rules, this gives a total usage of t + y + 1 + y + (r - y) + (3t(t-1)) + 3 = 3t² - 2t + y + r + 4 creature types. For the cyclic-tag-in-StackFlow program above, we have t = 5, y = 20, r = 41, for a total usage of 130 creature types; large, but not so large that it is impossible to find enough creature types to implement the program. (This construction does not attempt to implement output, nor any of the optimizations suggested above.) The actual required usage is in fact 129, because halt rules have no reason to maintain the invariants on the toughness of the head of the stack; thus, there is no symbol required for the second push of the halt rule, because it can be omitted without causing issues.
Finally, we need to handle the start and end of the program. Starting the program is simple enough: we get all the stacks set up appropriately (via token creation and manually placing counters); place, copy, and edit the text of all the support cards (the Dralnu's Crusades, Engineered Plagues, etc.); float a huge amount of mana; ensure nobody has any cards remaining in hand apart from the cards needed to fulfil the rest of these steps; destroy all irrelevant permanents (e.g. with a combination of Oblivion Stone and Armageddon); exile all cards from graveyards that have any abilities that have an effect from there (if any were used to set the gamestate up), e.g. via Tormod's Crypt; and finally "manually" pop stack 1 via simultaneously reducing the toughness of all the creatures in it (and no other creatures) by 3, with the last remaining card in the any of the players' hands, and spending all the resulting mana. Although it is awkward to get such a specifically targeted toughness reduction, we can use damage instead (a creature which has taken 3 damage acts identically to a creature whose toughness is 3 lower for the purposes of this construction); there are many cards that can accomplish this (such as the classic Fireball, given enough mana).
For ending the program, we need to implement halt rules, in addition to the implementations of push/pop rules given above; that is, implement "whenever a creature type dies, a specific player loses the game". This can be accomplished using Vengeful Dead, the same way as in Alex Churchill's construction, which directly kills a player on 1 life (and is protected from Noxious Ghouls using Blades of Velis Vel, as with the other creatures that exist only for their triggered ability), and it is simple enough to arrange for the players to be on 1 life in advance. One interesting extra possibility to note is that who wins the game depends on the controller of the Vengeful Dead, which otherwise doesn't matter, and thus different "halt" rules in the program can cause different players to win.
Taken together, all this constitutes a proof that there are Magic gamestates for which the eventual outcome of the game (win, lose, or draw) depends on an arbitrary computable unsolved problem. In fact, because the players have no further decisions once the machinery of the abilities has been set in motion (and with no cards in hand nor relevant abilities they can activate), the players can simply announce that they are passing priority until the end of the turn (explicitly permitted by the Magic tournament rules), at which point the game immediately ends, but it may require solving an arbitrarily difficult problem in order to determine which of these events actually happened; although the rules oblige players to attempt to break up infinite loops, this restriction does not exist when the players have no opportunity to do so.
See also Alex Churchill's research on the computational class of Magic: the Gathering; Alex Churchill, Stella Biderman, Austin Herrick "Magic: The Gathering is Turing Complete", prepub 2019
In the description of the Magic: the Gathering implementation, you write
- However, the Reanimator does have to wait for state-based actions, whereas the Noxious Ghoul that looks at the global-toughness-decreasing type triggers as soon as the token is created, and thus the Reanimator's effect enters the stack second and so resolves first.
This seems bogus, because all triggered abilities are put to the stack together after all state-based actions are processed. The state-based actions don't determine the order the triggers go to the stack. – b_jonas 12:55, 10 January 2015 (UTC)