Re: Fourvoyé

https://www.quora.com/Is-the-game-of-GO-Turing-complete

There is not any way to give a generalized Go game an unbounded amount of space, so Go cannot represent a Turing machine tape.

However, Generalized Go, with Japanese ko rules, is EXPTIME-complete. That means that if a yes/no ("decision") problem can be solved by a Turing machine, using an amount of time that grows exponentially with the problem size, then that problem can also be represented by an equivalent Go position on a suitably large board.

So, Go is powerful enough to represent any problem in NP, like the Travelling Salesman Problem. It can embed much harder problems like deciding whether a quantified boolean formula is true, or any other problem in PSPACE. It can even simulate a Turing machine for a fixed number of steps. It’s not powerful enough to solve doubly-exponential problems like the decision procedure for Presburger arithmetic.

https://cstheory.stackexchange.com/questions/18885/is-there-a-generalization-of-the-go-game-that-is-known-to-be-turing-complete a trois réponses qui sont un très bon complément.

"It is seldom that liberty of any kind is lost all at once." ― David Hume