A year or two ago, I created a combo that proves Magic to be Turing complete. I put up a little website about it. Now it's doing the rounds of the internet (Reddit, BoingBoing, Kotaku, Metafilter, Slashdot, Mark Rosewater's Tumblr), so I thought I really ought to post it on the official Wizards boards.
The basic idea is to assemble a universal Turing machine out of Magic cards, so that a massive cascading sequence of triggered abilities occurs which simulates computation of a Turing machine, without needing any interaction from the players at all. It's mainly a load of ETB and LTB triggers, with the core being six copies of Teysa, Orzhov Scion (coexisting via Mirror Gallery ), all extensively hacked with Artificial Evolution and Mind Bend .
The questions I had to answer include:
Q: How do you make a tape extending arbitrarily far in two directions with a "step left" and "step right" operation?
A: The tape to the left of the head is a series of Ally tokens, one 1 toughness away from dying, one 2 toughness away, etc; and the tape to the right is a similar series of Zombie tokens. To move left, we give all Allies +1/+1 and all Zombies -1/-1 (creature types adjusted as appropriate ). This causes the smallest Ally to die, and a different ability triggers depending on what colour it was.
Q: How do you simulate the vital Turing machine concept of multiple states?
A: Phasing! All the Teysas are enchanted with Teferi's Curse or similar, and we arrange for the machine to cast Time and Tide whenever it needs to change state.
Q: How the heck do you cast an instant as a triggered ability?
A: Chancellor of the Spires , with help from Aether Flash , Skirk Drill Sergeant , Wheel of Sun and Moon , False Dawn , Artificial Evolution , and lots of Engineered Plague . Simple, right?
Q: Can you really prevent players needing to do anything?
A: ...Almost. The key operation "Give all Allies +1/+1" is accomplished via Kazuul Warlord , which unfortunately has a "you may" in his rules text. So the cascade of triggered abilities isn't completely requiring no input from the players: one player has to effectively keep saying "yes" every time Kazuul Warlord or Chancellor of the Spires asks him "do you want to do this?" Another player has to similarly keep saying yes every time Skirk Drill Sergeant asks him the same question. But other than those "always say yes" operations, there's no interaction by the players required at all.
Q: Does this mean we can implement Magic Online inside another game of Magic?
A: Theoretically, yes. But it might take quite a long time to get past the loading screen.
Full details at www.toothycat.net/~hologram/Turing/
I actually thought about this a week ago. I was thinking "Magic cards interact with each other, perhaps you could build a computer out of a combination of them."
But I almost instantly abandoned the idea because I remembered that Magic was able to emulate sentience with a single card .
So what do you plan to use it for?
will parts of it be able to work better than a classical turing machine?
Or is it just something you wanted to figure out and did?
I created it basically because someone asked me "Is Magic Turing complete?" I figured the answer must be yes, and started to try to prove it, and eventually (with help from a few friends) came up with that intricate combo.
also if you let yourself use un cards, magical hacker on noxious ghoul lets you play the role of warlord without involving a "may". doesn't eliminate the player choices but reduces them.
or, in real magic world, put out a second noxious ghoul of each type and a goldnight commander . then you have each creature getting +1/+1 and each non-X creature getting -2/-2, resulting in each non-X creature getting -1/-1. with no choices made.
also you can reduce them by finding a way to sacrifice/kill the chancellor and having mikaeus the unhallowed in play. (with a way to remove the counter, obviously, but that's trivial.) I don't know a way to remove the chancellor decision though, that one's tricky.
Good stuff. The concept of the stack where each action resolves in sequence is the same as the stack an operating system's kernel works with, right?
I opened your website and immediately thought, "There's no way I'm getting through all of this."
I opened the Wikipedia page for Turing Machine and immediately thought, "There's no way I'm going to understand this."
But something kept me going, and I now have a basic understanding of Turing Machines and I actually read your entire site! Thanks for introducing me to this whole concept, and amazing work figuring out how to do this in Magic. It's unfortunate that we now know it isn't actually universal (according to Wikipedia anyway), but the groundwork is still awesome, and it sounds like you've already made a truly universal one with your 18-color version.
Also, kudos to razoborne for making a contribution so quickly.
tl;dr I'm in love with automated logical processes and this is awesome.
Edit: Reading the Wikipedia article further, I see that the validity of Alex Smith's proof is in debate. Just wanted to ammend my above statement about the (2, 3) Turing machine not being universal.
If you can't stay within the limits of four copies of any card (except ones which remove the restriction), it's pointless to construct the turning machine. You're just using Magic cards and their abilities to describe something you could more efficiently write out for yourself. Why even bother to use Mirror Gallery when you've already rejected a core-essential rule? What's the difference from writing out a Turning Machine based on random abilities and operations than using Magic cards if you're not going to stick to all the rules? It's no different. It removes the point of using Magic cards since the entire basis of it is that you're working within those limitations to construct a complex operation.
Maybe you're just trying to force it because you feel that there is some academic reward, but there isn't. People who have completed far greater works have yet failed to receive the grandeur you might be expecting to get for completing this. For example, take a look at John von Neumann, he's contributed so much and seemingly for nothing. The world barely recognizes him today, he isn't even a vaguely well known figure. Now take a look at Steve Wozniak, he was all the muscle behind Apple. He is the one who did all the hardest work (like the electrical engineering) and even most Apple users don't even know he exists. They (and everyone else) give all the credit to his right hand man, Steve Jobs. Not saying that Jobs doesn't deserve credit, and there are hidden elements to this (like Wozniak's hidden nature, preferring to stay under the radar), but it's another example of how people who contribute extreme measures get nothing out of it.
Thought you had compleated Turing.
Prepared for encoming Phyrexian armageddon.
I never looked into the concept. My comment is based on the details of exceeding the card limit of four (in the event of such a thing). I didn't have the time to check into it and I just wanted to drop my insight on the matter in case more than 4 actual copies were being used. Sorry for the misunderstanding.
You crashed the Matrix.
Could someone create this situation in MTGO and compute something simple? This becomes ten times more epic if it happens. I'd settle for a video of it happening at a table, to show off the idea.
I'm not sure you could do it on MTGO. is carnival of souls on there? how about aether flash ? then again carnival isn't necessary if you give A a mikaeus the unhallowed , animate the aether flash, and give it a blight sickle . or if for some reason you can't animate all enchantments you can just use argent mutation and then karn's touch it.
RazorBorne, all those cards are on MTGO. Only some of Ice Age block and earlier is missing.
I want to voice my praise and admiration for an amazing feat.
Since the Turing tape is built of tokens, it didn't seem immediately obvious to me that the four-of rule would interfere. However, since a particular type of token is required, and cards are needed to generate tokens, I suppose that is where the problem comes in, as opposed to in the construction of the "machine", the tape reader and player, itself.
Since the players are required to say "yes" to some actions, though, this may not meet some definitions of "Turing-completeness" as applied to a game... but the fact that it can be used to compute anything with the cooperation of the players does mean that it meets a reasonable definition of Turing-completeness.
Riptide Replicator can easily be engineered to create tokens of any type, color, and size, and it can be reset at will with Vedalken Mastermind + Freed from the Real . Even if a single player is going to be responsible for bringing almost all the cards involved, they can, since all sorts of Clone effects would suffice for the fifth and sixth copies of Teysa, and likewise Copy Enchantment for extra Cloaks of Invisibility.
I mean, you could just buy a computer with orders of magnitude larger processing power for the cost of a subscription, but details.
Last I checked, Magic Online has a limit of 200 tokens at a time, so if the tape needs to be longer than that to express your calculation, you're out of luck anyway.
Heh. In my two attempts to run the combo on MTGO, I've indeed used the Argent Mutation - Karn's Touch trick to animate Dralnu's Crusade followed by a kicked Rite of Replication . Infinite mana is definitely useful: since I'm already using Kazuul Warlord and making my other creatures Allies, I use the Harabaz Druid - Freed from the Real combo for that. Most useful in bootstrapping it all is making all 4 decks contain 4x Noble Benefactor , which will happily block each other at every opportunity: that makes the combo much quicker to set up. It's also very valuable to have a Bazaar Trader with Freed from the Real to pass things around between the players. But MTGO doesn't let you make multiplayer games with no time limit; 2h or 2h30 is the longest it lets you give each player, and even my machine chugs when running 4 copies of the MTGO client, such that even using F4 and F6 as much as possible, the driving player runs out of time. (It doesn't help that Artificial Evolution 's effects only display if the creature type is singlular in the original rules text! So hacking Dralnu's Crusade , you have to remember which ones you've evolved...)
It's looking like in order to make a proper universal Turing machine, I can't use the 2-state-3-colour one; that one needs the tape to be initialised in an infinitely nonrepeating way to do computation. It seems that 2-state-18-colour is what we need. That can be accomplished with creature types instead of colours, using loads and loads of Rotlung Reanimator s. Even that is doable on MTGO: there are enough Clone variations to get 36 nontoken Reanimators easily, and if each deck has 4 of each of Teferi's Curse , Cloak of Invisibility and Copy Enchantment , that's enough for 36 phasing enchantments. Version 5 of the Turing machine will have all the details when I get it online.
what are you gonna use for the +1/+1 and -1/-1? you can get a non-may +1/+1 through hacking life and limb s and baru, fist of krosa but I don't see a way to give non-may -1/-1s based on color. or may-based ones, for that matter.
PS: is there a way to force you to make copies of something as a triggered ability? if so you can use two death's-head buzzard s as long as bird isn't one of your key creature types.
Unfortunately, that isn't going to be extensible to anything beyond Shamans, since reentering a zone causes object modification to reset, and it's not even possible to keep re-hacking with Artificial Evolution because the ability has already triggered by the time it could be used, and it can't touch triggered abilities that are already on the stack.
Even making token copies of a Rage Forger doesn't work because layer-3 effects aren't copiable.
I was just intending to clarify SadisticMystic's misconception.
And that's what happens when I post without first getting the necessary understanding of the context. Sorry about that, and please disregard.
What is the point of a computer made out of Magic cards? How would you do that? Can it even run Crysis?
if you use the hex and gale, make sure to have a painter's servant set to black so hex only deals 1 damage.
well, two with furnace. but the point is to avoid it dealing 4.
Now, to throw in the Uncards so that we can achieve the internet...
So if you run MTGO on this, and then set up this situation on MTGO, you'd have Inception?
Okay, version 5 is online:
I've fixed the universal Turing machine, changing it from the (2 state, 3 colour) one (which wasn't properly universal unless the tape is infinitely large and nonrepeating) to a (2 state, 18 colour) one which is widely accepted. I've also eliminated the fiddly Skirk Drill Sergeant - Carnival of Souls - False Dawn - Platinum Emperion - Wheel of Sun and Moon madness in favour of a much more sensible approach, involving Necroskitter and a Tajuru Archer wielding a Blight Sickle .
Meanwhile, I'm still plugging away at v6. Omen Machine looked promising at first, but its "players can't draw cards" proved annoying; but Wild Evocation has a lot of promise. Rather than fiddling around with burn spells that only damage a selected subset of creatures, I think it'll work much more simply to hack Righteous War , and use either Pyroclasm or Evincar's Justice . Bereavement along with Wheel of Sun and Moon let me make one player discard their burn spell and the other get to cast it. There are still a bunch of details to figure out, though, which have been proving rather fiddly and annoying. I'm pretty confident I'll get there.
And even if that approach doesn't pan out, Khoth has an outline of an astonishing alternative approach, which would even allow more than 2 states! And it's built on, of all things, Life and Limb , Muraganda Petroglyphs , and - I'm not making this up - Cathedral of Serra :D
This is all great work.
Once the "you may" is sorted i'd like to see a video of a game starting, drawing cards each turn and setting things up, then performing a basic but algorythmic calculation.
in the cards section, you have both Slith and Siren marked as S1. FYI. also Blinkmoth and Bringer are both at times marked as B1.
really cool. unfortunate upswing in "may" abilities with the archer and skitter, but a lot less fiddliness with mana so it's all good. and as far as I can tell you can still cut that down with a goldnight commander .
Wasn't it confirmed that you can make an infinite combo with Niv-Mizzet, the Firemind and Niv-Mizzet, Dracogenius on the field on a same turn? o_o"
You wouldn't be doing anything, just drawing cards. Probably would be good havng Venser's Journal or Reliquary Tower on the field. Hell, add Laboratory Maniac if you're worried of killing yourself in the process.
That has nothing to do with the Turing Machine, and if a loop makes progress toward finishing the game (such as dealing damage to players or taking cards out of your library), it isn't really an unbounded loop, is it?
Hi all. Thought I'd let you know that I believe I have version 6 of the combo ready. This is the version with no "may" abilities anywhere: everything's completely forced once the combo is fully set up. I'm hoping that some of you might be up to reading through the combo checking it works and even offering suggestions for simplifying it.
The basic idea is fairly simple, and it turns out to make normal processing almost as quick as in v5, and changing state is even simpler than it was. Unfortunately, to handle running out of tape I've had to add an entire extra player, bringing the combo up to 5 players. I'm definitely looking for ways to reduce the number of players involved.
The setup of version 6 is as follows:
This time execution proceeds over multiple turns, one turn-cycle per step. The tape is controlled by Alex as before, with blue token creatures representing the tape to the left of the current head (the closest at 1/1, next-closest at 2/2, etc) and green tokens to the right. The tokens have one of eighteen creature types corresponding to what "colour" the space is. Like before, we use two sets of 18 Rotlung Reanimator s double-hacked by Artificial Evolution , one set phased out, all controlled by Alex.
But as well as those 36 phasing Reanimators, we also now have another set of 36 phasing Rotlung Reanimator s, all controlled by Cathy. This is because I'm using Cathars' Crusade rather than Kazuul Warlord to get non-optional +1/+1 counters, which makes it really fiddly to use "messenger" tokens under the tape player's control. Cathy's array of Reanimators make temporary tokens to control tape movement & state changes as I'll explain later.
(Granting all 72 Reanimators phasing without using token Auras is faintly fiddly, but perfectly doable. Details Show
Teferi's Curse and Cloak of Invisibility grant 8 x the number of players; Copy Enchantment another 4n; using Argent Mutation , we can get another 8n from Sculpting Steel and Phyrexian Metamorph ; and there are tricks with Mizzium Transreliquat and Infinite Reflection to get as many more as we like.)
All 5 players have Wheel of Sun and Moon , empty library, and one card in hand. Graveyards can be as full as you like. There's a Wild Evocation which forces each player to play their card on their turn, unless they've been forced to discard it by a trigger from Bereavement ( hacked to trigger off black creatures dying). The card is cast during their upkeep, goes to library rather than graveyard on resolution thanks to Wheel of Sun and Moon , and then gets drawn in their draw step.
The tokens on both halves of the tape are pumped up by Cathars' Crusade , triggered by the new token arriving. To shrink one half by 2 (to net a shrink by 1 after cancelling out the pump from Cathars' Crusade), we either have Denzil cast Ember Gale or Emily cast Kaervek's Hex . Painter's Servant to black makes Kaervek's Hex only hit the green half of the tape, Furnace of Rath doubles the 1 damage from each burn spell to 2, and Everlasting Torment makes the damage permanent. We make sure the burn spells only damage one half of the tape by using a few Ivory Mask s so Alex is the only legal target player for Ember Gale , and letting the leftwards Reanimators make blue tokens and the rightwards ones green tokens.
So each turn cycle, either Wild Evocation makes Denzil cast Ember Gale targeting Alex, shrinking the left half of the tape, and Emily doesn't get to cast Kaervek's Hex because she was forced to discard it; or vice versa. We can also use Bereavement to make Cathy either cast or discard Time and Tide , depending on whether we want a phase change or not. (Because each step is a different turn, Time and Tide plays the opposite role to v1-5: we cast it when we want to stay in the same state as before, because all the Reanimators phase at the start of Alex's turn anyway!)
When a token on the tape dies, that triggers Reanimators to make a new token for Alex; and also Cathy gets to make a temporary messenger token. This messenger token dies immediately to Aether Flash , and will in turn create another messenger token for either Denzil or Emily. Between these two tokens we get either one or two triggers of Bereavement , making Denzil discard Ember Gale or Emily discard Kaervek's Hex , and perhaps also Cathy discard Time and Tide .
I want processing to happen on Alex's turn, not on Denzil's or Emily's, because that could lead to getting two Turing steps in one cycle. So Alex has two Glorious Anthem to make all the tokens one point larger than they'd have to be to die when Ember Gale or Kaervek's Hex resolve. I make them temporarily two points smaller on Alex's turn by having the spell that Alex casts off Wild Evocation every turn be Infest . So it's in Alex's upkeep that the smallest token actually dies, having got a -1/-1 counter in Denzil's or Emily's.
So this all handles normal movement and state changes very smoothly. Halting the machine is also easy, using Vengeful Dead . Unfortunately, noticing when we're out of tape is a whole lot harder.
This is what Bob does in the new version. He also has a Reanimator watching for any of the messenger tokens that are normally produced on Alex's turn, making him discard his card. If we're out of tape, then when Alex casts Infest and nothing dies, Bob will fail to discard his card, and be forced to play it instead.
His card is Azorius Chancery , the only land to feature in the combo. It's forced to bounce itself; but first, a trigger resolves from a Seed the Land , controlled by Cathy and hacked with Artificial Evolution to make creatures of type Colour 1 of the tape. The Seed the Land token dies immediately, triggering machine execution just as if the tape had included a Colour 1 token at that point. Execution happens on Bob's turn rather than Alex's, but that doesn't matter: fortunately the order that triggers go on the stack doesn't affect much now things are spread across multiple turns.
Further choices are removed by giving everyone Blazing Archon and/or having copies of Light of Day hacked to all colours, and exiling all lands apart from Bob's Chancery in hand so nobody even has the opportunity to tap anything for mana.
So that's the proposed setup. I'll be writing this up for the website over the next week or so.
If anyone can see any bugs in the combo, please tell me. And if you've got any ideas for simplifying it, I'd love to hear that too.
I'd especially like to make the running-out-of-tape handling not need a whole other player, but it's pretty fiddly: there aren't many things that trigger on "whenever a creature doesn't die".
It's somewhat complicated by the way that I'm also avoiding ever letting two (or more) abilities trigger for the same player for the same event: after all, then the player would have to make a choice (which order to put them on the stack), and we can't have that, can we? This makes it rather fiddly because Cathars' Crusade does have a habit of triggering off all the same things I want to notice. Any ETB triggered abilities in the machine basically can't be under Alex's control, because then they'd need ordering relative to Cathars' Crusade's trigger.
There are some possible changes that seem like simplifications, but that would require different creature types when writing a Colour12 space to the left vs writing a Colour12 space to the right. But that'd require a whole array of hacked Dralnu's Crusade s, at least 18 of them and probably 36, and I'm quite glad to have got away from the hordes of Crusades: the current version of v6 doesn't include any at all!
I've considered trying to combine two of the spellcasting players into one using Paradox Haze , but conditionally discarding the second card is very hard and the only player who unconditionally casts a spell also has Cathars' Crusade preventing them from using Bereavement to discard the first one. (But perhaps something could be arranged with Helm of the Ghastlord or Pain Magnification ?)
one problem: how does the machine stop Bob from just playing the Chancery? it makes him discard before his turn, but then he draws it and passes through his main phase without playing it. that is an active decision to not act he has to make every turn, unlike every other aspect where action is impossible. the only way I can see to prevent it is to give one player territorial dispute and eon hub but you're currently using each player's upkeep in some way so that would require an additional sixth player.
that's not true, I can think of another way (replace the masks with runed halo s and have someone who plays solfatara every turn on Bob) but that still requires Felix.
I actually just had an idea but it's complicated and I need to run, I'll explain when I get back.
Bob has the ability to manually play his bounceland if he so desires, creating an extra (and possibly erroneous) tape step. That's probably a bug. You can counteract this with Limited Resources plus ten lands that have no effect, like the Seafarers' Quay cycle.
Creating extra copies of the phasing Auras is really quite simple: play one of the Copy Enchantment s choosing not to copy anything, animate it, and then a regular old Clone can chain through its copy effect and choose an Aura to copy.
Also, with Painter's Servant on black, a single Light of Day is sufficient to stop all attacks, and compactness is at least worth something when the combo is taking so many cards as it is. Just make sure you don't accidentally kill the Servant.
Good catch all! I was tossing up a few different ideas for Bob's card. I thought Seed the Land + a bounceland was better than the other options, but I was definitely wrong.
why bother with the germination? why not just use, like, kird ape ? your triggers don't have to be tokens, do they?
there seems to be a little information missing. how do Cathy's messenger tokens create tokens for Denzil and Emily? do they also have rotlung reanimator s? if so that should be mentioned.
also if you wanted to you could replace painter's servant with darkest hour . doesn't really accomplish anything though.
Darkest Hour doesn't work because it overwrites colors, rather than adding to them, so that it won't be possible to distinguish left and right with different colors.
I have a combo you could use to make your Rotlung Reanimator s. With a Volrath's Shapeshifter in play and a Essence of the Wild on top of your graveyard, any creature that comes into play under your controll will be a Volrath's ShapeShifter . Then just put a Rotlung Reanimator on top of the yard. The Wheel of Sun and Moon you're already using protects them, and they are just as hackable . And because they are not tokens they work just fine with phasing.
This is because Volrath's Shapeshifter uses a a text changing effect to gain the Essence of the Wild 's attributes. Then when another creature enters the battlefield the replacement effect from the essence applies to the copiable attributes in layer one. Making the creature a shapeshifter, which then gets its own text changing effect.
A simple Cursed Totem will shut down the ability to tap creature-lands for mana, without requiring prearrangement for them all to be tapped, and since the whole point of the combo is to be mandatory, shutting down activated abilities (which are all discretionary) isn't such a bad idea anyway. It would take care of things like the ": Discard a card" on Volrath's Shapeshifter too.
The tricky part is arranging it so the Reanimators are all Saprolings (and thus forests, and thus phasing) but no other creatures are, because you don't want anything else suddenly disappearing. The easiest way is probably a hacked Olivia Voldaren , which can go away once setup is complete.
Aurelia, the Warleader made me think of this again, particularly in conjunction with Hellraiser Goblin , for arbitrarily many forced attacks. Granted, you need a triggered way to flicker Aurelia; Slithery Stalker perhaps. Restoration Angel is so close to being right for the job...
Then again, version 6 seems to have things under control, and has removed the Spellbinder that required all that combat in the first place. It might be interesting to remove the Time and Tide requirement by switching the attacked player through some sort of exile or control-switching effect, but that requires rewriting the whole engine. I'm not entirely sure it would even work yet.
I also noticed Spelltwine as a single-turn way to force-cast a particular spell, but the only good way to avoid problems with the user's choice of which spell to cast first precludes using it to cast another copy of itself.
There are two problems in the arrangement. One is that you cannot have Bereavement changed to black because of the Painter's Servant making everything black; change it to red or white instead. The other problem is that Furnace of Rath doubles the damage from Æther Flash too, which is too much; that can be solved by adding two more Glorious Anthems, or you can replace all four with a Gavony Ironwright .
Instead of Cathars' Crusade, you can use Borborygmos enchanted with a colour-changed Sinister Strength that has a later timestamp than Painter's Servant, an attacking requirement, and Worship . This allows using tokens of some other types to mark the ends of the tape which set off triggers to continue computation as appropriate and also to re-create them, removing Bob.
Bereavement is supposed to hit black and trigger upon anything dying. Furnace of Rath is a wrinkle, but one that can easily be fixed by changing it to Sulfuric Vapors , again hacked to black because everything is black. Unlike Furance of Rath, Sulfuric Vapors only works on spells dealing damage, so it will increase the damage from Kaervek's Hex or Ember Gale without touching the triggered ability on AEther Flash.
Post Your Reply
Please login to post a reply.