Please create an account to participate in the Slashdot moderation system


Forgot your password?
Math Games

Magic: the Gathering Is Turing Complete 135

TsukiKage writes "A 50-card M:tG combo for four players is demonstrated that is used to construct a simple Turing machine, performing arbitrary computations just by following the rules of Magic and card text thereafter."
This discussion has been archived. No new comments can be posted.

Magic: the Gathering Is Turing Complete

Comments Filter:
  • I see... (Score:5, Funny)

    by NIK282000 ( 737852 ) on Tuesday September 11, 2012 @09:21PM (#41307765) Homepage Journal XKCD comic in the near future.
  • Finally! (Score:5, Funny)

    by sirboxalot ( 791959 ) on Tuesday September 11, 2012 @09:22PM (#41307769)
    A use for Carnival of Souls.
  • by Gideon Wells ( 1412675 ) on Tuesday September 11, 2012 @09:33PM (#41307833)

    Like we /.ers are to talk about nerds or geekiness. Half of us would install a toaster in our cars just so we could have a toaster to install linux on while stuck in traffic. Yeesh.

    • I used to play M:TG until it got all complicated with poison counters. Playing started to hurt my head after just one drink. I suppose there are people whom enjoy it all the more with their superior short-term memory capacity compared to my own. Either way, at some point a game can get so complicated that it's no longer fun to play. As always, YMMV.

      • You should have moved on to V:TES (or Jyhad, as the old time players still call it). It was Garfield's second game, which he explicitly designed from the ground up as multiplayer instead of 1 on 1.

        A) Card rarity is linked to how many copies you'd likely want in your deck, regardless of the strength of the card (and there are no card limits).

        B) As a less mechanistic and more social game by its nature, it's quite conducive to drinking while playing, on many levels.

      • by donaggie03 ( 769758 ) <{moc.liamtoh} {ta} {reyemso_d}> on Tuesday September 11, 2012 @10:47PM (#41308327)
        That's one of the reasons for the 2 year set rotation. Only the last 2 years worth of cards are allowed in standard play. (There's also the obvious reason of requiring people to buy more cards.) There haven't been any cards with poison counters in at least the last 2 expansions (that's when I started paying attention to the game) and I'm pretty sure there's none in the upcoming one either. The developers try new and different things to try to keep the game fresh and interesting to long time players, and it seems to be hit and miss. I think they've been fairly decent at hitting, but poison counters are a good example of a miss, afaic.
        • by alzoron ( 210577 )

          The last two years have actually seen a resurgence of poison counters. Starting with the 2010 Fall Block of Scars of Mirrodin and the follow up expansion New Phyrexia in 2011 they combined the Poison and Wither mechanics together to create the Infect mechanic. Anyone that was discouraged by poison before would probably not be to happy with it more recently.

          • I started playing about a month before 2013 came out and so far I haven't seen many of the cards you describe. Maybe I haven't noticed because I didn't know they existed, I don't know. Luckily, those sets are going bye-bye in October anyway.
        • by Anonymous Coward

          No, the main reason is that they want to sell more cards. It's also a real bitch playtesting many different revisions of cards. I personally quit playing a bit after 4th edition came out. In those days the game would be very complicated if you were still using Alpha Beta and or Unlimited cards as you'd have classes of cards that no longer existed. I think the one that pop to mind were the mono artifiacts.

          Some of the counters were kind of cool, I liked Goblin Warrens, but IIRC it had issues with balance and

      • So you made MTG into a drinking game as well?

      • That's weird, I have the opposite observation, I used to play when I was a kid and recently restarted playing to show my 12 yo and I feel like everything is so simple now. They are no more "flip a coin card" and no more card that the text is so long that it fills up the whole space and is written in minuscule letters.
      • They did make a silver bullet card for poison decks [], but it's also pretty useful when played in conjunction with creatures with Persist, like this one []. Instant win condition.
    • by Hatta ( 162192 )

      MTG deserves vitriol, not because it's geeky, but because it's a money sink. Why spend a lot of money buying deck after deck when you can buy one RPG rule book and play indefinitely?

      If you want to play cards, we can play bridge or euchre, or hearts or spades, or bullshit. I'll even buy a special deck so we can play Uno. But what I won't do is buy deck after deck looking for the cards that give me an advantage. That's what's objectionable about MTG.

    • ...install a toaster in our cars just so we could have a toaster to install linux on while stuck in traffic.

      Genius! ... back in a minute... I've just got to go, umm, buy something...

  • Amazing (Score:5, Insightful)

    by DJ Jones ( 997846 ) on Tuesday September 11, 2012 @09:34PM (#41307837) Homepage
    Now this is truly "News for Nerds"

    Speaking of, what the hell happened to the motto? When did that happen?
    • I now have a suggestion for the new logo.
    • Now this is truly "News for Nerds"

      Too bad it fails at the "stuff that matters" part. (Just being snarky. I find the article interesting actually.)

    • by pjt33 ( 739471 )

      This is very definitely olds for nerds. But then you didn't read the article, so you didn't see the date.

  • My thoughts... (Score:5, Interesting)

    by madmarcel ( 610409 ) on Tuesday September 11, 2012 @09:51PM (#41307909)

    My thoughts in order:
    - Have I got the cards to do this?
    - What cards could I substitute to achieve the same thing?
    - Could I optimize or simplify this and reduce the number of required cards?
    - Do *really* I want to sit down and figure this out?
    - Could I simulate this in one of the many (open source) mtg cardgame engines?

    • People have already made complete processors on minecraft. I believe that's the limit on recursive computational implementation on today's hardware.
      • So make a Turing computer that acts as a Minecraft server, then emulate a 32-bit CPU on Minecraft on M:TG, then run Linux on Minecraft on M:TG...

    • by AK Marc ( 707885 ) on Tuesday September 11, 2012 @10:02PM (#41307971)
      Does the computer run faster if you have more rare cards in the deck?
    • It would be nice if their explanation actually made sense, if you wanted to do this.

      Specifically, this

      We use Skirk Drill Sergeant to cause the Chancellor of the Spires to repeatedly enter the battlefield, and Wheel of Sun and Moon to put it back into Denzil's library. No special tricks need to be done to get the Time and Tide card back where we want it, as the Chancellor lets the instant go back into Bob's graveyard when it resolves.

      ...makes no sense. Skirk drill sergeant doesnt apply to chancellor (a sphinx), and even if it did, it doesnt help you cast it over and over and over. It just helps you get it out of your library once the drill sergeant dies, assuming you modify the text to apply to sphinxes.

      That whole setup seems to make no sense whatsoever.

      • Re: (Score:3, Informative)

        by Anonymous Coward

        You have to actually read the explanation. They're manipulating cards' text with the cards "Artificial Evolution" and "Mind Bend", and then using the drill sergeant to pull the chancellor from the deck. He then dies to a combination of the ghouls + aether flash, and gets wheeled back into the library.

        Seriously, this is all in the "How it works" part of the explanation, and it does make sense. It's not something that could ever come close to happening in a normal game, but it obeys the rules if the situat

    • What I want to know is if you could actually get this combo off in a game. Even with all four players colluding, I think it would be difficult. Manipulating the Chancellor of Spires to the top of the Library would be one of the more difficult aspects. I wonder if you'd need any other cards they didn't include to make it a "playable combo" (e.g. Library of Leng to increase hand size).

  • I don't think that this is valid.
    1) "...following the rules of Magic"
    2) "At any time, three Teysas are in play"
    Back when Legends were originally released, you could only have one Legend card in play at a time. If another player summoned them, the previous Legend card had to be destroyed. Has that rule changed?
    • Re: (Score:2, Informative)

      by Anonymous Coward

      They have that covered with Mirror Gallery, which eliminates the Legend Rule while in play.

      • Yup, I should have rtfa before I replied (below). For completeness, the card text of Mirror Gallery is simply: The "legend rule" doesn't apply.
    • The cards are now called "legendary creature" or "legendary land" etc. The cards have creature names or land names, but their type is legendary creature. You can have more than one legendary card in play, but not more than one with the same name. It's a slightly different rule, but your point is still valid. You cannot have 3 "Legendary Creature - Teysa, Orzhov Scion" cards in play at the same time. As soon as the second card is played, both the first and second card go bye-bye.
      • so you can destroy an opposing legend by playing your own copy? is that intentional?

        • Yes, and in fact, it makes for lots of lulz when you play a clone for 4 mana, and end up with the only copy of a specific legend. Alternatively, have a vesuvan doppleganger out, and if they ever play a legend you can just copy it at the start of your upkeep.

          Clone / Doppleganger / Licid decks are so much fun....

  • ... because it's kind of a pointless exercise. After all, Conway's "Life" game was turing complete, and that had like, what? Maybe 3 rules?
    • If you can build NAND gates (or NOR gates for that matter) out of your materials, you have everything you need to build a Turing-complete machine.
  • Recursive (Score:5, Funny)

    by IorDMUX ( 870522 ) <mark,zimmerman3&gmail,com> on Tuesday September 11, 2012 @11:42PM (#41308715) Homepage
    Do you realize what this means?

    Given sufficient time and mana, we could simulate a game of Magic within a game of Magic!

    Vaguely related []
  • It's only fair to point that this article was generated out of this question on Draw3Cards [] (Disclaimer: I'm the owner of D3C)
  • by kav2k ( 1545689 ) on Wednesday September 12, 2012 @03:47AM (#41309977)

    Any sufficiently advanced technologyis indistinguishable from Magic.

  • you can make Turing complete also Yu-Gi-Ho, Scopa [] and even Monopoly.
    Anyway, next week I'll demonstrate that SlashDot is Turing complete and NP-hard at the same time.

    • Read the article again - while the situation is contrived (a bunch of players aren't likely to ever accidentally create a Turing Maching during a Magic game), they are following all the rules of the game - no external cheats required.

      Pretty sure you're not going to pull that off in Monopoly.

      • ... is it ok for you to slightly change the meaning of a few cards just to accommodate the experiment?
        If so, also Monopoly will be OK. More or less.

        • ... is it ok for you to slightly change the meaning of a few cards just to accommodate the experiment?

          I think you're missing the part where they're "slightly chang[ing] the meaning of a few cards" via actual Magic cards.

  • Use a MTG Turing Machine to create a computer running Minecraft, then use that implementation of Minecraft to create a MTG Turing Machine simulator.

  • It gets better! Because the behavior of the underlying hardware in a Turing machine is considered axiomatic and unfailing, the following M:tG CR sections:

    104.4b If a game that’s not using the limited range of influence option (including a two-player game) somehow enters a “loop” of mandatory actions, repeating a sequence of events with no way to stop, the game is a draw. Loops that contain an optional action don’t result in a draw.
    716.1b Occasionally the game gets into a state in which a set of actions could be repeated indefinitely (thus creating a “loop”). In that case, the shortcut rules can be used to determine how many times those actions are repeated without having to actually perform them, and how the loop is broken.
    716.3 Sometimes a loop can be fragmented, meaning that each player involved in the loop performs an independent action that results in the same game state being reached multiple times. If that happens, the active player (or, if the active player is not involved in the loop, the first player in turn order who is involved) must then make a different game choice so the loop does not continue.

    mean that this M:tG Turing machine solves the halting problem! The consequences of the fact that, without the halting problem, a Turing machine would never have been described are left as an exercise for the reader.

"The Avis WIZARD decides if you get to drive a car. Your head won't touch the pillow of a Sheraton unless their computer says it's okay." -- Arthur Miller