[rulusidaze]

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/

[ajkjk]

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]

>rules of MtG are Turing Complete

Yes, but only if you are:

>using them as your notation

From the linked article:

>The machine below just extends this idea

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.

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.

[TheRealPomax]

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]

I know I shouldn't bite, but I just want to so bad...

>so all you've said is

Actually 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 cool

I 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 not

I 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]

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]

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?

[kbenson]

> 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.

[valbaca]

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]

>there is a set [...with] mechanics

Welcome 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]

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]

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/...

[GuB-42]

"Shahrazad" had the potential to make impossibly long games, possibly even undecidable with the right combo. It has been used to force draws by stalling games.

For that reason, it is now banned in all tournament formats. In fact, it is the only "normal" card to receive this treatment.