Hacker News: AlexTFish

New comment by AlexTFish in "The rule says, “No vehicles in the park”"

AlexTFish — Sat, 24 Jun 2023 11:53:07 +0000

To me it looks like the emergency vehicles are counted as violating the rules by about 60% of players? Which I assume is meant in the sense of "yes, this technically breaks the rules, but we assume they had good reason to (because they were following higher-scope rules)".

New comment by AlexTFish in "Magic: The Gathering is Turing Complete"

AlexTFish — Tue, 07 May 2019 13:21:25 +0000

FWIW that's my old site, showing the 2012 version of the result, which required cooperation between 4 players. The version in the paper on arXiv is the result of my latest research (with Stella and Austin) where we get it down to 2 players and eliminate all choices required by any player.

I am planning to update the toothycat.net site pretty soon with this new result, though.

New comment by AlexTFish in "Magic: The Gathering is Turing Complete"

AlexTFish — Tue, 07 May 2019 13:19:54 +0000

As the other repliers have explained, MtG provides various ways to circumvent that. Thus we found ways to encode millions of pieces of state in tokens, and we ensured that the game loops round computing the Turing machine execution one step at a time.

Your sentence "There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large" is actually key. You're completely right - there are many. What's unusual about our result here is that we found a way to embed a fully functional Turing machine inside not an arbitrary extension of a board game, but inside a board game exactly the way it's normally played.

New comment by AlexTFish in "Magic: The Gathering Is Turing Complete (v5)"

AlexTFish — Fri, 02 Oct 2015 15:22:45 +0000

The Shahrazad deck also presumably needs either Plains or Black Lotus.

New comment by AlexTFish in "Magic: The Gathering Is Turing Complete (v5)"

AlexTFish — Fri, 02 Oct 2015 12:30:29 +0000

This isn't an error. The machine doesn't use phasing to trigger enter-the-battlefield triggers, merely to switch between the two states (sets of Rotlung Reanimators watching for the current token dying).

New comment by AlexTFish in "Magic: The Gathering Is Turing Complete (v5)"

AlexTFish — Fri, 02 Oct 2015 12:29:38 +0000

The machine as demonstrated on that page requires 4 players. There are probably ways to do it with fewer, but you might have to accept situations where two abilities trigger and the players need to choose an order to put them on the stack (though it makes no difference either way).

New comment by AlexTFish in "Magic: The Gathering Is Turing Complete (v5)"

AlexTFish — Fri, 02 Oct 2015 09:12:02 +0000

On the "Cards" page, http://www.toothycat.net/~hologram/Turing/Cards.html:

> The first sixteen Reanimators were cast in the normal fashion, four by each of the players, and donated by a Bazaar Trader. The other twenty are Clones and Vesuvan Shapeshifters copying a Rotlung Reanimator. The phasing enchantments can include Teferi's Curse, Cloak of Invisibility, and Copy Enchantment, cast by any player and donated by a Bazaar Trader. These creatures and Auras must not be tokens, because tokens disappear when phased out.