News for hackers. Stuff that matters.
Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Thursday November 16, 2017 @11:33AM (#15713985)
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

Re:Magic: The Gathering Is Turing Complete (2012) by gowld on Thursday November 16, 2017 @02:20PM (#15715636)
Are you sure the constant is enormous? https://arxiv.org/abs/1606.00484
Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Thursday November 16, 2017 @02:34PM (#15715764)
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"

?

Re:Magic: The Gathering Is Turing Complete (2012) by btilly on Thursday November 16, 2017 @04:04PM (#15716602)
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.

Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Thursday November 16, 2017 @06:03PM (#15717514)
I'm not saying QuickSelect has a large constant. I am saying the median of median O(n) algorithm, which again is not QuickSelect, has a large constant.
Re:Magic: The Gathering Is Turing Complete (2012) by btilly on Thursday November 16, 2017 @07:37PM (#15718057)
And I am saying that when you combine the two you get an algorithm with a small constant in practice and guaranteed O(n) behavior in the worst case.

For example do quickselect on 9/10 rounds but on every 10th round do a median of medians. The overhead of guaranteed performance will only be a few percent off of the average.

Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Friday November 17, 2017 @07:21AM (#15721389)
That's very cool. However, the anecdote I was sharing for comparison purposes specially referred to the median of median algorithms. This was also many years ago, long before the paper above was written.

I'm not saying that it's impossible to do it and always will be. Re-read what I've said if you like, and you'll see I am simply sharing an anecdote for the purposes of an analogy about this particular situation.

Re:Magic: The Gathering Is Turing Complete (2012) by lmartel on Thursday November 16, 2017 @09:19PM (#15718447)
This didn't make intuitive sense to me so tried to Google it. Is "Introselect" what you're referring to? https://en.wikipedia.org/wiki/Introselect

It's a hybrid of quickselect and median of medians, but the switching strategy's a bit more complicated.

Re:Magic: The Gathering Is Turing Complete (2012) by btilly on Thursday November 16, 2017 @10:22PM (#15718646)
Introselect is a more complex version of the same idea.

But basically both quickselect and median of medians are divide and conquer. Median of medians is an expensive way to guarantee a good division. Quickselect hopes for one.

If quickselect goes well, then median of medians will be relatively cheap when run because it is run on a much shorter list. If quickselect does not go well, the median of medians passes guarantee progress. So average behavior is only slightly worse, and worst case behavior is still nicely bounded (albeit with a much worse constant).

Re:Magic: The Gathering Is Turing Complete (2012) by megaman22 on Thursday November 16, 2017 @02:47PM (#15715900)
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.
Re:Magic: The Gathering Is Turing Complete (2012) by lmkg on Thursday November 16, 2017 @02:56PM (#15715998)
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.
Re:Magic: The Gathering Is Turing Complete (2012) by pdpi on Thursday November 16, 2017 @06:42PM (#15717732)
If you keep the number of samples constant (so that you can have O(1) time) then the quality of the estimate goes down with the number of items in the collection. To keep the quality constant, you need number of samples to scale with the size of the collection.
Re:Magic: The Gathering Is Turing Complete (2012) by Retric on Thursday November 16, 2017 @10:09PM (#15718608)
Depends on how you are measuring accuracy.

Suppose I have a set of all integers less than k and > 0, and you after N random selections want to estimate k. Presumably as k increases your accuracy drops in absolute terms. But, if you do the same thing using the reals so there is infinite number of numbers from zero to k you can still make a bounds for k.

Granted there are now infinite number of reals in your estate, but you can still pick an N such that an arbitrary % of the time k is +/- an arbitrary % of your guesses.

Re:Magic: The Gathering Is Turing Complete (2012) by contravariant on Thursday November 16, 2017 @07:03PM (#15717855)
Not necessarily, using k samples you can estimate the mean of i.i.d. samples with a variance of 1/k the sample variance. Note that this is independent of the sample distribution, in particular it's also true if you're drawing from some fixed collection, regardless of its size.

I find it harder to say something about the median, but I imagine some similar theorems hold.

Unless you have some definition of quality for which you can show that you do need more samples with a bigger collection?

Re:Magic: The Gathering Is Turing Complete (2012) by nlperguiy on Thursday November 16, 2017 @11:53AM (#15714200)
But the constant is not large. O(n) quickselect is extremely fast algorithm.
Re:Magic: The Gathering Is Turing Complete (2012) by chowells on Thursday November 16, 2017 @11:57AM (#15714247)
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.
Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Thursday November 16, 2017 @12:05PM (#15714341)
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.
Re:Magic: The Gathering Is Turing Complete (2012) by ekelsen on Thursday November 16, 2017 @02:13PM (#15715562)
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).
Re:Magic: The Gathering Is Turing Complete (2012) by sova on Thursday November 16, 2017 @02:24PM (#15715673)
Wow. can't believe no one ever mentioned this before, Most Significant Bit bucketification would cut down seek time a lot.
Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Thursday November 16, 2017 @11:54AM (#15714210)
Oh, you should have seen my implementation then.
Re:Magic: The Gathering Is Turing Complete (2012) by zitterbewegung on Thursday November 16, 2017 @12:11PM (#15714389)
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.
Re:Magic: The Gathering Is Turing Complete (2012) by opportune on Thursday November 16, 2017 @12:50PM (#15714765)
Have you ever heard of an omega or theta bound?
Re:Magic: The Gathering Is Turing Complete (2012) by alexanderstears on Thursday November 16, 2017 @02:08PM (#15715508)
I might have - give me a minute to check the owner's manual for my hypercomputer.
Re:Magic: The Gathering Is Turing Complete (2012) by colordrops on Thursday November 16, 2017 @12:58PM (#15714849)
Reasonable is relative.
Re:Magic: The Gathering Is Turing Complete (2012) by specialist on Thursday November 16, 2017 @12:30PM (#15714586)
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.
Re:Magic: The Gathering Is Turing Complete (2012) by gitgud on Thursday November 16, 2017 @05:25PM (#15717248)
"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

Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Thursday November 16, 2017 @03:50PM (#15716492)
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.com/Pages/Card/Details.aspx?multiver...

[2] Storm keyword ability; e.g. Dragonstorm: http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

Re:Magic: The Gathering Is Turing Complete (2012) by HelloNurse on Thursday November 16, 2017 @04:35PM (#15716864)
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.

Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Thursday November 16, 2017 @05:05PM (#15717110)
>> 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.

Re:Magic: The Gathering Is Turing Complete (2012) by praptak on Thursday November 16, 2017 @04:26PM (#15716778)
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_automaton

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

Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Thursday November 16, 2017 @05:16PM (#15717190)
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.aspx?multiver...

[2] http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

Re:Magic: The Gathering Is Turing Complete (2012) by Smaug123 on Thursday November 16, 2017 @05:48PM (#15717416)
"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.

Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Friday November 17, 2017 @04:09AM (#15720391)
Yes, that's exactly what I'm saying- why is it not the point? If you were trying to prove that Java is Turing-complete you wouldn't look at all the Java programs ever written and try to build a Turing machine with those programs. Instead, you'd use the symbols in the language to write a (new) program that simulates a Turing machine, or a set of functions that suffice to prove Turing completeness.

The proof the author has given is equivalent to building a Turing machine out of existing programs in his language of interest. M:tG cards have instructions printed on them in the ability text language - so those instructions, rather than the cards themselves are the symobls in the language. The cards are best seen as scripts or small programs written in that language.

But why should anyone restrict themselves to existing cards when trying to prove the Turing completeness of the language?

Note, also, that the rules of well-formed sentences in the ability text language are given in the M:tG Comprehensive Rules or at least some of them are- there's no complete formal definition of the language. Still, there's plenty enough for anyone to be able to form syntactically correct ability text.

So, again- if you're trying to prove the Turing completeness of a language, why would you not use the full expressive power of the language to compose new strings? And instead restrict yourself to just a few pre-existing strings of it?

Re:Magic: The Gathering Is Turing Complete (2012) by rcxdude on Friday November 17, 2017 @12:14PM (#15723851)
The game of 'Magic: The Gathering' consists of both the rules and the cards available in it (which are written in a kind of language). If you are printing your own cards, most players would agree you are not really playing 'Magic: The Gathering', but your own homebrew game based on it.
Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Friday November 17, 2017 @12:48PM (#15724173)
Maybe, but if we're doing formal proofs then we're not in the realm of opinion anymore. So the point is to substantiate any claim as to what, exactly, is reasonable to call "the mtg language". I really doubt there's any context in which a language can be formally described as "a limited number of texts"... especially if that language is supposed to be Turing complete (which implies non - finite-ness) !

BTW, the kind of language the ability text language is, has a name: it's a Controlled Natural Language. [https://en.m.wikipedia.org/wiki/Controlled_natural_language].

As to the relation between the language and the rules, if you think about it, if the language is not equivalent to the rules, then it can't represent (and, therefore, modify) every rule in the game (as it is supposed to). And if the language and the rules are equivalent, then proving one is Turing complete also proves it for the other. So you can ignore the rules and focus any proof on the language.

Re:Magic: The Gathering Is Turing Complete (2012) by YeGoblynQueenne on Friday November 17, 2017 @12:58PM (#15724274)
Just to make it plain. In formal language theory, a language is a set of symbols and a set of rules that determine what is a valid string.

Given such a definition of the ability text language, you don't need to restrict yourself to only those strings that are actually printed on cards.

In the same sense, we don't define the English language as every text ever written in English - but as some unknown formal system that can produce an unknown, probably infinite, number of strings that includes all text ever written in English.

So why treat the M:tg language any different?