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 &quot;It&#x27;s O(n), but the constant in the front is enormous, so it&#x27;s usually totally impractical&quot;. The reply has stuck with me ever since: &quot;I doesn&#x27;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.&quot;<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&#x27;t to make something practical, it was to prove <i>it can be done</i>. Now all that&#x27;s left is finding a practical way to do it too.<p>[0]<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Median_of_medians" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Median_of_medians</a>