7 ms·
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 toge
by mabbo 9y 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 https://en.wikipedia.org/wiki/Median_of_medians
- nlperguiy 9y agoBut the constant is not large. O(n) quickselect is extremely fast algorithm.
- mabbo 9y agoOh, you should have seen my implementation then.
- chowells 9y agoQuickselect 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 9y agoYeah, 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 9y agoIf 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 9y agoWow. can't believe no one ever mentioned this before, Most Significant Bit bucketification would cut down seek time a lot.
- zitterbewegung 9y agoThere 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.
- opportune 9y agoHave you ever heard of an omega or theta bound?
- alexanderstears 9y agoI might have - give me a minute to check the owner's manual for my hypercomputer.
- colordrops 9y agoReasonable is relative.
- deleted 9y ago[deleted]
- specialist 9y agoYa, 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 9y 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 9y agoAre you sure the constant is enormous? https://arxiv.org/abs/1606.00484 https://arxiv.org/abs/1606.00484
- mabbo 9y agoThe 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 9y agoI 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 9y agoI'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.
- pdpi 9y agoIf 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.
- contravariant 9y agoNot 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?
- YeGoblynQueenne 9y agoWell, 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?multiverseid=109718 http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver... [2] Storm keyword ability; e.g. Dragonstorm: http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=370537 http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...
- praptak 9y agoFor 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 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.