Magic: The Gathering Is Turing Complete (2012)
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.<p>You miss this point.<p>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 <i>possible</i> to accomplish this task in linear time. It might not have been."<p>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 <i>it can be done</i>. Now all that's left is finding a practical way to do it too.<p>[0]<a href="https://en.wikipedia.org/wiki/Median_of_medians" rel="nofollow">https://en.wikipedia.org/wiki/Median_of_medians</a>