|
|
|
|
|
|
by kragen
912 days ago
|
|
|
mtg is more recent than things like the johnniac, but plausibly there's a traditional card game with the same criteria that predates electronic computation but then we have to ask thorny ontological questions: does a card game count if it requires a particular configuration to be turing-complete, but nobody ever played it in that configuration? what if nobody ever played the game at all? what if nobody even knew the rules? |
|
|
> Prior to this work, no undecidable real games were known to exist. Demaine and Hearn (2009) [10] note that almost every real-world game is trivially decidable, as they produce game trees with only computable paths. They further note that Rengo Kriegspiel {Rengo Kriegspiel is a combination of two variations on Go: Rengo, in which two players play on a team alternating turns, and Shadow Go, in which players are only able to see their own moves.} is “a game humans play that is not obviously decidable; we are not aware of any other such game.” It is conjectured by Auger and Teytaud (2012) [1] that Rengo Kriegspiel is in fact undecidable, and it is posed as an open problem to demonstrate any real game that is undecidable.
> The approach of embedding a Turing machine inside a game directly is generally not considered to be feasible for real-world games [10].
Regarding your ontological question, that we don't know if something is Turning complete doesn't mean it isn't.
People explored the Game of Life before it was proven to be Turing complete. The 1970 SciAm article says "Conway conjectures that no pattern can grow without limit." so Martin and Gardner didn't even know about gliders then. People don't say GoL wasn't Turning complete in 1970.
I pointed to a 1998 paper claiming the Z3 machine from the 1940s was Turing complete, that author clearly believes that a particular physical configuration is not required.
Nor did Turing construct a physical representation for his paper.
FWIW, the MtG preprint gives a concrete example of a 60-card initial deck. I would be surprised if neither the authors nor anyone else has ever tried it.
The ontological question is even more fully resolved because no one has ever created a real Turing machine. We always have the proviso "if given enough memory".
Similarly, the video game "Minesweeper" is NP-complete as the size increases, and with an infinite board - clearly not physically realizable - is Turing complete. https://en.wikipedia.org/wiki/Minesweeper_(video_game)#Compu...