GOPHERSPACE.DE - P H O X Y
gophering on hngopher.com
HN Gopher Feed (2017-11-16) - page 1 of 10
 
___________________________________________________________________
Magic: The Gathering Is Turing Complete (2012)
180 points by reimertz
http://www.toothycat.net/~hologram/Turing/index.html
___________________________________________________________________
 
maxiepoo - 5 hours ago
As someone that does not understand the rules of Magic, how do they
get around the fact that a Turing machine requires infinite memory?
Presumably a particular game of Magic has a finite set of cards and
probably states too?
 
  deepnotderp - 5 hours ago
  Tokens or an infinite blink (exiled and returns) mechanism I
  think. I haven't seen the thing in a while :)
 
    staticautomatic - 3 hours ago
    You can also go infinite with time warp and a means of fetching
    it from your graveyard.
 
  valbaca - 4 hours ago
  Many Magic cards can create "tokens" which don't count as cards,
  but can operate in the same way as cards in many ways.You can
  have as many tokens as you can create. The MTM (Magic Turing
  Machine) seems to rely on this.It's actually within the rules to
  "go infinite" with tokens. For example, you have a Foo which taps
  (is spent) to create a Bar token. The Bar token can untap (reset)
  Foo. Since you can do this as much as possible, within the rules
  you effectively just simulate that you can repeat the combo, pick
  a number (100, 1 million or 1 Googolplex), and you have that
  many.The proof is much more complex than that, using various
  creature types (zombie, rats, etc.) and other game states, but
  that is how the infinite memory problem can be overcome.It's also
  worth noting that the infinite memory requirements is often
  ignored when showing Turing Completeness.(I play a lot of Magic
  and just took a glance at the page)
 
    dragontamer - 4 hours ago
    The tape is actually very simple.+1/+1 counters on Zombies
    represent the tape to the right. +1/+1 counters on Yetis
    represent the tape to the left.Whenever you reach the "end of
    Tape" (ie: All your Zombies are now Yetis), there's a trigger
    that creates a new Zombie token. Effectively creating "infinite
    tape". I didn't read to see how it worked on the "Yeti side",
    but I presume its the same concept.Moving the tape back and
    forth is about putting -1/-1 counters on Yetis and +1/+1
    counters on Zombies, or vice versa. Death triggers convert
    Yetis into Zombies and vice versa.There are 18-states
    representing the "tape head" (which I presume to be the current
    creature with zero counters on it). I haven't really looked
    into how it works, but "Halt" state is pretty amusing actually.
    The "Halt" state kills all players, which "Halts" the program.
 
  [deleted]
 
  xaedes - 3 hours ago
  huh? - so we can never build turing machines? because we can
  never build infinite memory?
 
    schoen - 3 hours ago
    True, no Turing machine in the strict sense is physically
    realizable!
 
cantrip - 6 hours ago
Previous
discussion:https://news.ycombinator.com/from?site=toothycat.net
 
pimmen - 5 hours ago
Absolutely awesome. I could probably talk for hours with this guy!
 
gt_ - 2 hours ago
I quit playing Magic in 1999 when my 4 friends and I found out we
were playing by the wrong rules.We went into town, to a tournament
at a comic shop, and saw the games taking 20 minutes. Ours took 1-2
days.We tried what was, to us, the ?new rules? and we were
disappointed, gave up. It was a big blow. Suddenly the cards were
less enchanted, the decks were less sacred. Maybe if I had
understood the Turing completeness of Magic, I would have had it in
me to start a tournament under our rules. Well, I still could if I
had written them down. I?m pretty sure they were the best rules.
 
  mirceal - 1 hours ago
  classic "i'm not quite sure and at this point i'm too afraid to
  ask"to be fair to wotc, learning and playing the game nowadays is
  pretty straightforward.
 
AgentEpsilon - 6 hours ago
No it isn't.I can forgive the extremely contrived decks, but using
a card to completely change the behavior of the majority of your
cards doesn't mean the game itself is Turing complete. If anything,
this is just showing how you can utilize Magic game mechanics to
create a Turing Machine.
 
  cgmg - 6 hours ago
  > this is just showing how you can utilize Magic game mechanics
  to create a Turing MachineI believe that is the point.
 
  rhaps0dy - 6 hours ago
  >the game itself is Turing complete [...] you can utilize Magic
  game mechanics to create a Turing MachineAren't those two
  statements equivalent?
 
    [deleted]
 
Rickasaurus - 6 hours ago
This idea inspired the 2011 ICFP programming contest, lambda the
gathering: http://icfpc2011.blogspot.jp/2011/06/task-description-
contes...
 
_Codemonkeyism - 6 hours ago
No it isn't.With some contrieved meaning of the cards, which has
nothing to do with the "meaning of the card" in Magic the game,
like "State B, Colour 16: Stay in state B, colour this space 18,
move one step right." it recreates a complicated and arcane turing
machine.
 
  aaachilless - 6 hours ago
  Words they've used like "State B, Colour 16: Stay in state B,
  colour this space 18, move one step right" are just mnemonics,
  for the sake of keeping track of information relevant to Turing
  completeness, that could be replaced by a description of whatever
  is actually happening in the game.
 
    _Codemonkeyism - 5 hours ago
    "colour this space 18"Thanks, didn't know "colour this space
    18" was a concept in MTG now, I haven't played for 2 decades I
    assume (stopped before Legends, no clue what came afterwards).
 
  gipp - 6 hours ago
  That's like saying a file on your computer is just a "contrived
  meaning" of the way magnetic domains are arranged on some glass
  platters in your hard drive.
 
    _Codemonkeyism - 6 hours ago
    It's like saying parking cars are turing complete, if a blue
    car means X and a red car means Y etc.'Reanimator 17B actually
    says "Whenever a Rat (R0) dies, make a Sliver (S1M).'The linked
    page is not using the rules of Magic the gathering or the texts
    on the cards, but uses it's own rules what cards mean.The game
    rules of magic the gathering are not turing complete, because
    the linked post is not talking about Magic the Gathering game.
 
      gipp - 6 hours ago
      Those aren't new rules for the cards that they're just
      contriving out of thin air. When it says that's what it
      "actually says", it means that's what the net effect of the
      card's actual text is in the environment that's been set up.
      It's just a rhetorical shortcut to help explain how the
      system works. All the cards are using the correct text as
      normal.
 
      dsp1234 - 6 hours ago
      This is like saying, "Draw go" isn't talking about MTG.  It's
      shorthand for all of the steps that you'd need to complete.
      Just like someone playing an Eggs deck is going to say
      "Casting KCI + IW, draw 2, float 2" or "Here is the main
      loop.  I'm going to do that until I hit banefire, then hit
      you for infinite damage."What's interesting is actual MTG
      gameplay uses a HUGE amount of shortcuts on every play,
      because saying every single thing you and the opponent have
      to do during each step and phase would be incredibly time
      consuming.
 
        crankylinuxuser - 5 hours ago
        Well, that gets weird. It can have shortcuts and also won't
        have shortcuts.If you play Commander or multiplayer, then
        its usually a heck of a lot less formal. Ive also played
        some local tournament games where the players were good-
        natured and we all just had fun.Then I've played some
        tournaments locally and at Gencon that were methodical and
        clockwork style "Please indicate what you did, step by ste-
        COUNTER". Or you get the priority police up and running,
        where you have to explicitly pass priority. I hate those
        games with a passion - it just drains the fun out via
        rules-lawyering.I've not played in a few years, primarily
        because the game was feeling much more like 'loot crates'
        that I've railed against prior. And with $3.50/pack, I
        didn't feel like I was getting enjoyment. You either buy
        buy buy, or get left in the dust and destroyed in games
        because you didnt buy buy buy.
 
          literallycancer - 4 hours ago
          >"Please indicate what you did, step by ste-
          COUNTER"What's the advantage over simply specifying the
          moment you wanted to react out of the last batch of
          actions (like a normal person)? If the opponent skips too
          many steps and gives up some critical information as a
          result -- his problem.
 
          mattnewton - 4 hours ago
          Because that leads to bad feels; did you counter X
          because you know I have Y in my hand now? I always try to
          explicitly pass priority after spells even in causal
          settings when I mean to.
 
          crankylinuxuser - 3 hours ago
          In a way, its an iterated prisoner's dilemma. Sure, I can
          construct a "infinite beatdown deck" that you lose 99% of
          the time. And guess what? I'll win.And that next game,
          they'll say "ditch that deck or you aren't playing".These
          days, I play explicit decks that have a neat theme and
          good win conditions (I have 2 decks left). They dont use
          infinite combos (they win, but are unfun), and I play to
          have a good time. If I lose, it was because I had some
          good threats and a blast of a game.
 
        _Codemonkeyism - 5 hours ago
        Thanks didn't know, I left MTG somewhre between Arabian
        Nights (or Antiquities, not sure) and before Legends.
 
          dsp1234 - 4 hours ago
          oh boy.  Wait until you hear about damage not using the
          stack...
 
          taway_1212 - 4 hours ago
          Actually, damage going through the stack was introduced
          around 6th edition. Back in the old days, damage worked
          the same way it works now.
 
  tdb7893 - 6 hours ago
  Isn't what states "mean" irrelevant to whether it's a Turing
  machine? I was under the impression that as long as it can
  simulate a Turing  machine (even an arcane or complicated one) is
  Turing complete and the state could be stored in anything (it's
  not like electricity has some special property that makes it
  better for Turing machines)
 
    pbhjpbhj - 5 hours ago
    >it's not like electricity has some special property that makes
    it better for Turing machinesTransmission, storage with
    magnetic interactions of electrical actions, small size of
    components, speed of transmission -- aren't these properties
    that make for more practical Turing machines?Parked cars are
    going to take ages to do anything useful with,
    no.(IANAComputerScientist)
 
      lou1306 - 5 hours ago
      Keywords "practical" and "useful". No one advocates parking-
      lot Turing machines for actual usage, but the fact is
      electronics only gives you speed and size improvements, while
      expressiveness remains the same.
 
      dsp1234 - 4 hours ago
      This is just a miscommunication of what "better" means in
      this context.No one disputes that a modern computer
      implementing a Turing machine is going to calculate faster
      than manually manipulating MTG cards.However, better here
      means 'more expressive'.  Turing completeness is concerned
      with whether or not a computational system is 'universal' or
      not.  In other words, whether that computational system can
      compute everything that another computational system could.
      If two systems can both be shown to simulate a Turing
      machine, then that means that those systems could compute the
      same exact set of things (given enough time).So with regards
      to expressiveness (or the things a system could theoretically
      compute), since a modern computer can implement a Turing
      machine and a MTG game can implement a Turing machine, they
      are both the same, and thus neither is 'better'.  In other
      words, the addition of electricity doesn't effect what a
      system could theoretically compute.
 
      klank - 5 hours ago
      More practical, yes. However, I believe the original poster's
      intent was that neither one is a "preferred" implementation
      from the perspective of the concept itself. There's no
      necessary tie between a Turing machine and electromagnetic
      fields. It's just that's what is easiest for us humans to use
      to implement it.
 
    klank - 5 hours ago
    You are correct.It is precisely this ability to map seemingly
    arbitrary and meaningless physical manifestations of turning
    machines to the abstract that provides the concept so much
    power. By being able to provably map the implementation to the
    concept you're able to get all the "benefits" of the concept
    without having to individually prove them in your
    implementation where it might be really difficult or just time
    consuming to prove everything individually.This,
    coincidentally, is the same reason mathematics is so obsessed
    with isomorphisms, homeomorphisms, homomorphisms etc. They are
    all different ways of saying "this thing stays the same, even
    when it changes" which many times means that things proven in a
    place where it's easy to prove are maintained in places where
    it's very difficult or even impossible to prove (absent the
    isomorphism).
 
mabbo - 6 hours ago
There lots of maybe-valid criticisms about this setup- oh, you have
to use so many game mechanics to make this work; you need to have 4
players all working together to do it and get just the right
conditions; this can never happen in real play.You miss this
point.Once, as an undergrad, I had just learned about the O(n)
selection algorithm (you can get the kth largest element in an
unsorted list in linear time for any value of k, which is
awesome)[0], and mentioned it to a grad student friend, but said
"It's O(n), but the constant in the front is enormous, so it's
usually totally impractical". The reply has stuck with me ever
since: "I doesn't matter if this particular algorithm has a big
constant. What matters is that this algorithm proves it is even
possible to accomplish this task in linear time. It might not have
been."Similarly, this Magic: The Gathering Turing Complete proof is
contrived, silly, impractical, and you are welcome to scoff at it
all you want. The point wasn't to make something practical, it was
to prove it can be done. Now all that's left is finding a practical
way to do it too.[0]https://en.wikipedia.org/wiki/Median_of_medians
 
  specialist - 5 hours ago
  Ya, the obligatory pendantics (concern trolling, nit picking,
  Eeyore-isms) is frustrating. I have a core group of nerd friends
  that are fun to play catch with. Any more, I?ve stopped voicing
  my crazy, weird, random, fun ideas to most people.
 
    gitgud - 34 minutes ago
    "Concern trolling" is a behaviour I've always noticed but could
    never describe.Mainly related to jealousy in my experience,
    with people trying to detour you with a myriad of concerns
 
  gowld - 3 hours ago
  Are you sure the constant is enormous?
  https://arxiv.org/abs/1606.00484
 
    mabbo - 3 hours ago
    The paper you've posted: "The Median of Medians (also known as
    BFPRT) algorithm, although a landmark theoretical achievement,
    is seldom used in practice because it and its variants are
    slower than simple approaches based on sampling."Me: "It's
    O(n), but the constant in the front is enormous, so it's
    usually totally impractical"?
 
      megaman22 - 3 hours ago
      I remember my algorithms class wasting like a week and a half
      going over that.  I'm still a little bitter.  There's only a
      few courses that I would have wanted a refund on my tuition
      for, and that's one of them.
 
      lmkg - 3 hours ago
      I'm not a domain expert, but I would assume that "approaches
      based on sampling" could be O(1). If so, the slowness would
      be based on the scaling, not on the constant.
 
      btilly - 1 hours ago
      But it is not impractical!Quickselect is trivial to write and
      has a much better constant on average, but can be O(n^2).If
      you do rounds of quickselect then occasionally a round of
      median of medians, you get guaranteed O(n) performance that
      on average is as close as you want to what quickselect does.
 
  zitterbewegung - 5 hours ago
  There are two types of algorithms . Ones we can implement with
  reasonable time. Then the others where we can?t implement in a
  reasonable time at this moment.
 
    colordrops - 5 hours ago
    Reasonable is relative.
 
    [deleted]
 
    opportune - 5 hours ago
    Have you ever heard of an omega or theta bound?
 
      alexanderstears - 3 hours ago
      I might have - give me a minute to check the owner's manual
      for my hypercomputer.
 
  YeGoblynQueenne - 2 hours ago
  Well, the proof is contrived, but that's not the point: it's also
  unnecessary and it may also be insufficient.To claim a system is
  Turing complete, what you need is (a) a store, from and to which
  you can read and write; (b) branching (if-statements); and (c)
  the ability to repeat instructions an arbitrary number of times
  (while-statements).It's easy to show that M:tG has all of the
  above: the Stack is a store; you read from and write to it when
  you place abilities on and resolve them from it. Branching and
  loops are present in ability text sentences like the
  following:You win the game if you control a land of each basic
  land type and a creature of each color. [1]When you cast this
  spell, copy it for each spell cast before it this turn. [2]As to
  a demonstration that the system actually works- you can point to
  any M:tG game.Finally- the proof in the OP may not be general
  enough. It uses only a limited sub-set of M:tG cards, so the best
  we can tell is that that specific sub-set of M:tG cards is Turing
  complete. For a more general proof, you at least have to explain
  why a specific subset is chosen and explain why you can
  substitute it with any other subset without loss of
  generality.The problem is that "card" is not a granular enough
  unit of the M:tG game to define as a symbol of an alphabet. A
  really general proof would make use of tokens of the ability text
  language. Such a proof would hold for any set of
  cards.___________[1] Coalition Victory: http://gatherer.wizards.c
  om/Pages/Card/Details.aspx?multiver...[2] Storm keyword ability;
  e.g. Dragonstorm:
  http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
 
    HelloNurse - 1 hours ago
    A formal system, in this case the game, is Turing complete if
    it can be used to implement a Turing machine. Complaining about
    using only a limited and very specific subset of available
    cards in a contrived way is like saying that a computer is not
    a computer because a large number of transistors aren't part of
    it, and if I rewire it randomly it ceases to work.Regarding
    "unnecessary", unlike typical competitive or recreational games
    in which players often do what they want, this particular setup
    results in an automaton in which players cannot disrupt the
    operation of the Turing machine:"The idea of my Magic Turing
    machine is that the players do nothing at all, except when the
    game offers them a choice."The article explains that the setup
    only allows choices to do optional actions, and it is assumed
    the players always do them. As "programming" human players to
    simulate a Turing machine would be too easy, they are replaced
    by mindless placeholders.If you used humans, they could follow
    the rules in their head (with written reference sheets); tapes
    could be lines of objects belonging to an alphabet of different
    types (e.g. coins of different countries and denominations,
    Barbie dolls of different model years, wax crayons of different
    colours), and the machine head would move by walking in front
    of the next tape position. No need to involve a proper formal
    system like a card game.
 
      YeGoblynQueenne - 54 minutes ago
      >> The article explains that the setup only allows choices to
      do optional actions, and it is assumed the players always do
      them. As "programming" human players to simulate a Turing
      machine would be too easy, they are replaced by mindless
      placeholders.Yes, I read that bit - I didn't realise it was
      meant to make things "harder". That alone is good enough to
      convince me the proof is unnecessary. If you can make a proof
      easier, then you make it easier. There's no need for harder
      proofs.Also, the fact that the proof does not involve human
      actions is another piece of evidence against the generality
      of the proof. You can model human choices as a distribution
      and allow for a fully-automated proof, that doesn't require
      human input in the strict sense. But leaving human actions
      out of the proof makes it less general- because the full game
      does involve such actions.
 
    praptak - 1 hours ago
    For Turing completeness it is not sufficient to demonstrate
    that a system has "a store". The store needs infinite capacity
    and random access. Infinite capacity alone is not enough - a
    stack has infinite capacity but a stack machine has
    demonstrably weaker expression power than a Turing machine:
    https://en.wikipedia.org/wiki/Pushdown_automatonSame goes for
    if-statements. The statements need to be general enough and
    work with the rest of the system to be usable to express the
    Turing machine. In particular your example of an if statement
    that starts "you win the game if..." makes this statement sorta
    useless, as it ends the computation. You can't make a Turing
    machine if every "if" ends the program. Same goes for any other
    "if" in the rules - they are usually pretty limited."As to a
    demonstration that the system actually works- you can point to
    any M:tG game."Again, that alone is not sufficient. It only
    proves that the system works for expressing one kind of
    computation, namely MtG games. For Turing completeness, you
    need to demonstrate that any Turing machine computation can be
    expressed as an MtG game, which is what the linked proof does.
 
      YeGoblynQueenne - 43 minutes ago
      There's no limitation on the size of the M:tG Stack, so it is
      infinite. Also, that M:tG uses a Stack as a store doesn't
      make it a pushdown automaton. For a pushdown automaton you
      need the stack to control decisions, but that is not the case
      here- there's still player actions and the effects of cards
      in the game etc.The if-statement I quoted is just one
      example. The following does not end the game:At the beginning
      of your upkeep, draw a card if you control the creature with
      the greatest toughness or tied for the greatest toughness.
      [1]The important thing to note of course is that the above
      are well-formed sentences in the ability text language. So
      the language allows if-statements and it doesn't matter how
      many cards with if-statements are actually printed.Also,
      strictly speaking, winning the game doesn't necessarily
      terminate processing. The ability of the card Shahrazad [2],
      for instance, creates a sub-game that may end without ending
      the original game:Players play a MAGIC subgame, using their
      libraries as their decks. Each player who doesn't win the
      subgame loses half his or her life, rounded up.Like I say, if
      you can show that the system has the components it needs to
      be Turing complete, then you've shown that it is Turing
      complete. Simulating a Turing machine is just another way to
      show Turing-completeness._______________[1] Abzan
      Beastmaster, http://gatherer.wizards.com/Pages/Card/Details.a
      spx?multiver...[2] http://gatherer.wizards.com/Pages/Card/Det
      ails.aspx?multiver...
 
        Smaug123 - 11 minutes ago
        "The language allows if-statements and loops" is not
        sufficient for the language to be Turing-complete. A
        language with loops in which the only form of selection is
        "if 4 > 3 then?" is not Turing-complete. Just pointing to a
        specific if-statement appearing on a card and saying "yeah,
        that's probably enough to make Magic Turing-complete" does
        not constitute a proof.I think you might be confused by the
        term "language". In the context of the proof, "language"
        means "anything that is the Oracle text of a card". You
        seem to be using it as "anything that could be printed on a
        card". I think you're saying "the game of Magic-but-
        where-I'm-allowed-to-choose-what-the-cards-say is Turing
        complete", which is undeniably true but also not the point.
 
  nlperguiy - 6 hours ago
  But the constant is not large. O(n) quickselect is extremely fast
  algorithm.
 
    mabbo - 6 hours ago
    Oh, you should have seen my implementation then.
 
    chowells - 6 hours ago
    Quickselect has an O(n^2) worst case, unless you use a variant
    like Tarjan's median-of-medians algorithm for selecting the
    pivot. And that does have awful constant factors.
 
      mabbo - 5 hours ago
      Yeah, this was the specific algorithm I meant. O(n) time, but
      in my undergrad implementation, it wasn't useful with less
      than billions of items, vs just sorting and selecting with
      highly optimized sorts.
 
      ekelsen - 3 hours ago
      If you are dealing with numbers, then you can do this is true
      O(n) time with radix-select.  (Basically do a MSB radix sort
      and only do subsequent passes in the bucket where you know k
      must be).
 
        sova - 3 hours ago
        Wow. can't believe no one ever mentioned this before, Most
        Significant Bit bucketification would cut down seek time a
        lot.
 
rulusidaze - 5 hours ago
A pencil and paper is Turing Complete. A bunch of rocks in a grid
is Turing Complete.[1]Sorry to be an ass but I can't even guess how
many "X is Turing Complete" things I've seen over the years.
Turing's point wasn't to define what can be a computer, it was to
define the limits of computation itself. Which is a far more
interesting topic, hence my irritation with this
post.[1]https://xkcd.com/505/
 
  valbaca - 4 hours ago
  True, but this is a game with no intention of being Turing
  complete. Yet there is a set of cards and mechanics within an
  "innocuous" game that resulted in a Turing Machine.
 
    rulusidaze - 4 hours ago
    >there is a set [...with] mechanicsWelcome to the definition of
    a Turing Complete system.Also the game in question is not
    "innocuous." The author admits to creating an artificial
    scenario under which a Turing Machine is possible.
 
      Yen - 3 hours ago
      I believe GP's point is that Magic: The Gathering was not
      intended to be a turing-complete set of rules and cards.I.e.,
      the game design was _intended_ to be entirely decidable.
      Indeed, certain game rules discuss what happens when events
      trigger each other in a loop - and if the loop is non-
      halting, the game ends in a draw. This rule is only
      meaningful if the halting problem for M:tG is
      decidable!However, in creating enough "relatively simple"
      cards, most of which are of the form "when one thing happens,
      another thing then happens", the designers of M:tG have
      managed to _accidentally_ create a non-decidable system.Sure,
      this particular example is contrived, but it has the
      implications that a non-contrived game state could find
      itself in an undecidable state! It is theoretically possible
      that a natural, tournament-level game could reach a state
      where it can't be decided if one player or the other wins, or
      if it's a draw. (Or, at minimum, deciding the outcome of the
      game might require sufficiently convincing a tournament
      official of your mathematical proof  that the game in fact
      will halt , within some known finite time).
 
        794CD01 - 2 hours ago
        The situation you describe isn't even that farfetched.
        There is a moderately popular deck called Four Horsemen
        that depends on repeating a set of steps to repeatedly
        shuffle your deck until the cards happen to be arranged in
        a sequence that allows you to
        win.http://www.mtgsalvation.com/forums/the-game/legacy-
        type-1-5/...
 
  ajkjk - 4 hours ago
  No, the interesting point is that the rules of MtG are Turing
  Complete, not that you can express something that's Turing
  Complete using them as your notation. That wouldn't be
  interesting at all.
 
    rulusidaze - 4 hours ago
    >rules of MtG are Turing CompleteYes, but only if you
    are:>using them as your notationFrom the linked article:>The
    machine below just extends this ideaThe author admits he has
    constructed an artificial scenario under which a Turing Machine
    is generated. This is exactly the same as using the rules of
    MtG as a notation to create a machine.A generalized set of the
    rules for the game Go is Turing Complete. A generalized set of
    the rules for the game Go Fish is Turing Complete.
 
      kbenson - 3 hours ago
      > The author admits he has constructed an artificial scenario
      under which a Turing Machine is generated. This is exactly
      the same as using the rules of MtG as a notation to create a
      machine.An artificial scenario which is achievable under
      normal play, and the only variation required by the human
      players being that when offered a choice, they choose
      affirmative.> A generalized set of the rules for the game Go
      is Turing Complete. A generalized set of the rules for the
      game Go Fish is Turing Complete.Do you have references for
      those?  I would be interested in seeing how they simulated
      the tape.
 
      TheRealPomax - 4 hours ago
      Okay, so all you've said is "Go is, interestingly, also
      Turing Complete". That is interesting and worth-posting-about
      information. In an attempt to illustrate the futility of the
      Mtg example with a Go example, you have in fact merely
      illustrated that in addition to Mtg, Go is ALSO interesting
      to look at.Mtg can be shown to be Turing Complete in one (of
      quite a few, actually) subset of rules. That's cool, and
      unexpected to many, and worth reading about.And that's true
      for any other example of things not usually associated with
      programming.(Turing completeness is an algorithmic property,
      not a "thing" property, so a pencil and some paper, or a
      bunch rocks, are certainly not Turing complete: you need
      procedural rules as well, something Mtg has no shortage of)
 
        rulusidaze - 3 hours ago
        I know I shouldn't bite, but I just want to so bad...>so
        all you've said isActually what I said was "a generalized
        set of the rules" for Go is Turing Complete. Go in itself
        is not, because the end-state of the game is indeterminate.
        Just as a "regular-ass" game of MtG without a very specific
        and artificial construction is not Turing Complete, in and
        of itself.>That's coolI can appreciate stamp collecting,
        and I don't want to say that it's an invalid use of time.
        There are plenty of worse hobbies. But my point is that any
        of an infinite, arbitrary, and inconsequential number of
        conceivable systems are "Turing Complete," and personally I
        don't find this very compelling.How many books in the
        Library of Babel[1] describe a Turing Complete
        system?>Turing completeness is/is notI stated as much in a
        comment below, or you could have inferred the same by my
        interpretation of the XKCD comic, but thanks for assuming
        I'm incompetent and acting in bad
        faith.[1]https://en.wikipedia.org/wiki/The_Library_of_Babel
 
          lmkg - 2 hours ago
          Are you making the distinction that most MtG decks are
          not Turing-Complete? Is that what you mean by "specific
          and artificial construction?"I think most people assumed
          that Turing-Completeness requires a specific and
          artificial construction, which is where the disconnected
          (and downvotes) are coming from. Especially for something
          wasn't previously believed to be a model of computation
          at all, much less a Turing-Complete one.
 
          salvar - 2 hours ago
          You seem to be taking a very hostile stance against what,
          a detailed and researched article about a project you
          don't deem worthy enough for your interest?
 
sethev - 6 hours ago
So mtgox could have been implemented in Magic: The Gathering.
 
  paulmd - 4 hours ago
  Surely it would have been implemented in Magic: The Gathering
  Online? ;)(MTGox was a trading site for virtual trading cards,
  not real ones.  It was "MTG Online: Exchange", not "MTG: Online
  Exchange"...)
 
    ggggtez - 2 hours ago
    Incorrect. MTGO is not a true turing machine because it doesn't
    have infinite tape.>The model of the tape is as follows.  A
    series of Zombie tokens controlled by Alex represent the tape
    to the right of the current headHowever, it seems that there is
    a limit to the number of creature tokens in MTGO which does not
    exist in the paper game.
 
      Smaug123 - 8 minutes ago
      For that matter, a physical digital computer has a bounded
      number of states it can be in, so it can't be Turing complete
      at all, if you're going to be really pedantic.You're only
      allowed to say MTGO is not Turing complete if you also agree
      that Java is not Turing complete (because the 32-bit JVM has
      bounded memory it can access).
 
    schoen - 3 hours ago
    I never knew that and never knew where the colon went! Thanks
    for pointing this out.
 
    fasquoika - 2 hours ago
    So fully written out it would be Magic: The Gathering Online:
    Exchange? It takes real courage to put two colons in a name...
 
_Codemonkeyism - 5 hours ago
OT: I have a MTG deck from somewhere between Arabian Nights and
before Legends. From those here that still play MTG, are cards
still anything worth?[Edit] Thanks a lot to everyone who answered!
 
  rsync - 5 hours ago
  Yes - old, rare cards (especially powerful ones that are now
  considered "broken") have only risen in value.They're also quite
  provocative.  Once every few years I'll break out my very, very
  old "power nine" deck and play with it at the local game store.
  All games stop.  Everyone comes to look.  People take pictures.
 
    mirceal - 1 hours ago
    I hope you play without sleeves and watch the other players
    shrivel... From time to time you should mumble: yes peasants!
    I'm that rich :) ahashahahahahahahzha
 
      rsync - 11 minutes ago
      Sleeves, definitely.The cards were not that expensive when I
      bought them in 1994/1995 ...
 
  lolive - 5 hours ago
  Yep! Even basic lands are worth 100$!  https://www.m.ebay.fr/itm
  /Mountain-Magic-Arabian-Nights-orig...
 
    mswiss - 55 minutes ago
    holy crap I didn't realize these were worth that much, I have
    boxes of these in my closet right now with cards from
    Unlimited/Legacy to Tempest(maybe some newer but i forget what
    the releases were called).Where's a good place to sell these?
    Ebay?
 
  empath75 - 5 hours ago
  Probably thousands of dollars.I couple of years ago, i found some
  old random magic cards from like revised with some dual lands and
  tossed it because I thought that they were still worth like $10 a
  piece.. turns out I threw away like $1500 worth of cards :(My
  original collection was stolen in 1995 and would be worth as much
  as McMansion today.  At the time it was worth about $5000.
 
    mod - 4 hours ago
    I sold my collection in about 2000. It wasn't worth 5k...mostly
    4th edition cards, and whatever expansions were out then.I sold
    it to my cousin for $75, which was cheap because I was doing
    him a favor, and he never paid me.
 
  malnourish - 5 hours ago
  It is highly dependent, but if you're curious you can check a
  website like tcgplayer.com and enter your cards in to get an
  idea. You'd want to look at the market value, rather than
  high/mid/low.Also consider that if you did want to sell, selling
  to a store drastically cuts value. Individual sales aren't
  without their share of problems either.I'm heavily involved in
  MTG, so if you did have further questions feel free to reach out.
 
jeremy7600 - 5 hours ago
Shouldn't this be (2012)?
 
  sctb - 4 hours ago
  Since we're not reading it in Japanese, yes. Thanks!