<p>Related:  Rengo Kriegspiel, a blindfolded, team variant of Go, is conjectured to be undecidable.</p>

<p><a href="http://en.wikipedia.org/wiki/Go_variants#Rengo_Kriegspiel" rel="noreferrer">http://en.wikipedia.org/wiki/Go_variants#Rengo_Kriegspiel</a></p>

<p>Robert Hearn's <a href="http://erikdemaine.org/theses/bhearn.pdf" rel="noreferrer">thesis</a> (and the corresponding <a href="http://www.crcpress.com/product/isbn/9781568813226" rel="noreferrer">book</a> with Erik Demaine) discuss this problem.  They prove other problems undecidable through "TEAM COMPUTATION GAME", which is reduced directly from Turing machine acceptance on empty input (see Theorem 24 on page 70 of the thesis).  So it seems to me that such a reduction would imply Rengo Kriegspiel is Turing complete.</p>

<p>On the other hand, their discussion says that this reduction would be very difficult (see page 123). So while this is a potential avenue, it appears that it has been looked into previously.</p>

CC BY-SA 3.0
2015-04-29T18:57:02.723Z
2015-04-29T18:57:02.723Z
SamM
<p>This is a build on my comment, with the idea of using shishos (ladders) as computations. It is merely an attempt to give a computation model that is based on Go, and for which it makes sense to ask whether it is Turing-complete.</p>

<p>We start by fixing some powerful but not Turing-complete computation model that always halts, for instance some typed $\lambda$-calculus, or primitive recursive functions. This is the "cheating" part as we use an external computation model, but it is a weaker one, so hopefully it is the game of Go which will fill the gap and make it Turing-complete.</p>

<p>We consider an infinite goban labeled by $\mathbb Z\times\mathbb Z$.
Now the initial configuration of the goban can be infinite, and is given by an algorithm from our formalism: given coordinates $(i,j)$ the algorithm says whether the intersection $(i,j)$  is empty, occupied by a black stone, or occupied by a white stone.
We fix a maximal size $N$ of the groups in the initial configuration.
This means that given a position, we can always compute the group occupying it and its number of liberties, or answer "invalid configuration".</p>

<p>We also fix a <em>marked</em> stone (say black) at coordinate $(0,0)$.
An initial configuration is valid if at the beginning the group of the marked stone has two liberties. </p>

<p>Now we can view this configuration of the goban as the initial configuration of a non-deterministic machine, where a transition consists in playing a white stone at one of the two liberties of the marked group.
At each step, black automatically answers at the other liberty.</p>

<p>The run ends if</p>

<ul>
<li>The marked group is captured, in which case the input is accepted</li>
<li>The marked group acquires more than $2$ liberties, in which case the input is rejected.</li>
</ul>

<p>The run can also continue forever...</p>

<p>As for non-deterministic Turing machines, the input is accepted if there is an accepting run.</p>

<p>It is easy to simulate this machine with a non-deterministic TM, thanks to the existence of the bound $N$ (which is a parameter of the whole model).</p>

<p><strong>Conjecture</strong>: For $N$ big enough (probably no more than $10$ to get the necessary gadgets), this model is Turing-complete.</p>

CC BY-SA 3.0
2015-04-29T13:49:18.173Z
2015-04-29T16:30:27.660Z
2015-04-29T16:30:27.660Z
Denis
<p>here is some evidence/ analysis/ results leaning against your conjecture that a Go generalization might be undecidable (aka "Turing Complete"); at least there does not seem to be a well known or commonly accepted case, and a search returns more results on the idea that its ("natural"?) generalizations are decidable. the generalization considered in this set of papers is PSpace complete. however, there are no "consistent" or "inevitable" ways to generalize games and it is conceivable someone could come up with a variant that is undecidable. </p>

<p>actually most nontrivial games probably can be modified or generalized in some way to have undecidable variants. (a famous simple game/ example along these lines proved "undecidable" by Conway is <a href="http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life" rel="nofollow">Life</a>.) the following references also point to many other references. </p>

<p>another line of thought might be that no game can be undecidable if it is winnable, ie undecidability works against the idea of games terminating with a winner in a finite number of moves. in other words maybe games are better/ more naturally analyzed as within the (decidable) complexity hierarchy as is typically the case.</p>

<ul>
<li><a href="http://www.levreyzin.com/presentations/Go.pdf" rel="nofollow">GO is PSpace hard</a>, by Reyzin, talk on result by Lichtenstein, Sipser</li>
<li><a href="http://www.computer.org/csdl/proceedings/focs/1978/5428/00/542800048-abs.html" rel="nofollow">GO is PSpace hard</a> by Lichetenstein, Sipser</li>
<li><a href="http://library.msri.org/books/Book42/files/wolfe.pdf" rel="nofollow">Go Endgames Are PSPACE-Hard</a>, Wolfe</li>
</ul>

CC BY-SA 3.0
2015-04-30T22:53:35.353Z
2015-04-30T22:53:35.353Z
vzn
<p>In my patent application - <a href="http://www.faqs.org/patents/app/20150102562" rel="nofollow">Turing Complete Sets of Game Components with Divinatory Elements</a> - I describe variants for game rules (including games played on a 19x19 Go board) which add a degree of complexity to games like chess and Go allowing for board positions to simulate linear bounded automata for an arbitrarily long period of time. As mentioned in the comments above, Go on an infinite board would introduce some difficulties as far as determining a game winner, since it is a game with a territorial objective, unlike chess. From my application: "Many other Turing complete game embodiments are possible, but I will give just two more brief descriptive examples to illustrate some other possibilities for adapting games to be played as Turing complete variants and then discuss ramifications. Games like Gomoku (SCARNE, p. 537) and Go (SCARNE, pp. 533-7) which are played on a 19×19 grid with two different colors of pieces are also candidates for Turing complete variants with divinatory elements. In the case of these games, Rogozhin's (2,18) UTM is used. This is also the UTM used by Churchill (2012) as cited in the prior art references. In order to create a game variant of this type, we will use coins for our game pieces. Prepare to play the chosen game variant by sorting large quantities of two different coins--pennies and dimes for example--into piles based on the date on their obverse sides. In this case, dates on the coins will be used as a substitute for colors in the context of the UTM instructions. Colors have been used for UTM instructions in the previously described embodiments, but this embodiment illustrates that another attribute of the game components, in this case a number, may be used. In the most general case, I will refer to this potential for substituting another attribute of the game components in place of colors as a use of a subset of the set of game components. Each player should start with 19 stacks of 19 of their chosen coin. Each stack of pennies and dimes should contain only coins with the same date--let's say, for example, 19 pennies dated 1991, 19 dimes dated 1991, 19 pennies dated 1992, etc. through 19 dimes dated 2009. A coin may only be played in the leftmost column of the board if it has a 1991 date, the next column to the right requires a coin with the 1992 date, etc. through to 2009 in the rightmost column. Play a game of Go or Gomoku as normal except for this rule regarding which pieces may be played where. When the (2,18) UTM is initiated based on pre selected game criteria (in a similar manner to that described in other embodiments) the UTM read/write head will read a heads up coin as being in state 1 and a heads down coin as being in state 2. A coin with the date 1991 will be considered an A coin by the UTM, 1992=B, 1993=C, etc. skipping over the year 2000. Coins are replaced by others with different dates according to the UTM instructions. As far as divinatory elements are concerned, there are 360 degrees in the zodiac and 360 intersections surrounding the central intersection on a Go board, so Sabian symbols (ROCHE) are an obvious fit. For more divinatory aspects of a Go board and game, see "The Religious Dimensions of Go" (SCHNEIDER)." Go game scenarios where a pre agreed UTM analysis of a board position might be useful include boards with <a href="http://senseis.xmp.net/?KoPagesTaxonomy" rel="nofollow">triple kos and boards with long ko fights</a>.</p>

<p>Is the trade off between adding additional complexity in rules in order to introduce Turing completeness to tabletop games worth the effort? Likely the answer to that question depends on the game and the players, but Magic: the Gathering is an example that in at least some cases the answer to that question is likely to be yes.</p>

CC BY-SA 3.0
2015-04-29T02:38:58.823Z
Your link only shows what look like "trading cards" without any discussion of Go that I can see. I think this is an advertisement for your patent and not an answer to the question.
Huck Bennett
CC BY-SA 3.0
2015-04-29T20:59:44.283Z
See the additional embodiments section beginning at paragraph [0135]. I'd quote it here but it won't fit. The gist is to analyse the board using Rogozhin's (2,18) UTM where the standard Go pieces are replaced by pennies and dimes (since they meet the two state requirement, having obverse and reverse sides) with 19 different mint dates (one date for each column on the board). A standard game of Go is played until some pre agreed trigger (triple ko or a ko fight perhaps) in the game mandates a UTM analysis of the board position.
Tom Cooley
CC BY-SA 3.0
2015-04-29T22:10:25.173Z
Sorry, I don't understand this at all. What you're describing still has a finite number of states, so it can't be Turing complete. More importantly, what do "divinatory elements" and "religious dimensions" have to do with anything?
Huck Bennett
CC BY-SA 3.0
2015-04-29T22:27:42.467Z
"Divinatory elements" and "religious dimensions" have to do with my patent (see patent title). As I said previously, what is being simulated is linear bounded automata for an arbitrarily long period of time which (if you trust Wikipedia) is generally what we deal with in the real world - http://en.wikipedia.org/wiki/Turing_completeness#Non-mathematical_usage
Tom Cooley
CC BY-SA 3.0
2015-04-29T01:38:26.437Z
2015-04-29T21:27:25.920Z
2015-04-29T21:27:25.920Z
Tom Cooley
<p>Is there a generalization of the GO game that is known to be Turing complete?</p>

<p>If no, do you have some suggestions about reasonable (generalization) rules that can be used to try to prove that it is Turing complete?  The obvious one is that the game must be played on an infinite board (positive quadrant). But what about in-game play and end game conditions?</p>

CC BY-SA 3.0
2013-09-06T09:27:33.307Z
You can also add in the question the reference to the [PSPACE-hardness proof](http://dl.acm.org/citation.cfm?id=322201) by Lichtenstein and Sipser (perhaps it can be used as a starting point)
Marzio De Biasi
CC BY-SA 3.0
2013-09-06T09:35:21.460Z
Maybe I'm lacking some background, but in what way is the question of Turing completeness relevant to the game of go? More generally, how can the game be said to *compute* anything?
mhelvens
CC BY-SA 3.0
2013-09-06T10:23:47.193Z
Hm... I guess you could see a given board position as the input and the eventual point-difference, assuming perfect play from both sides, as an encoding of the output. Interesting...
mhelvens
CC BY-SA 3.0
2013-09-06T10:47:02.620Z
If you're playing on a finite board, it can't be Turing-complete. And I'm baffled as to how you decide when a Go game on an infinite board ends.
Peter Shor 
CC BY-SA 3.0
2013-09-06T11:00:25.063Z
@PeterShor: a possible (reasonable?) generalization can be: start playing on $n \times n$ with an initial configuration that represents the input; the winner scores +1, extend the board to $(n+k) \times (n+k)$ (or $2n \times 2n$ or only horizontally to $2n \times n$ ???) and continue to play without removing old stones, stop the sequence of matches and end the game when the difference of scores is greater than $deltawin$ (or alternatively when a fixed computable function $f(score1,score2) = true$).
Marzio De Biasi
CC BY-SA 3.0
2013-09-06T18:03:33.087Z
think author doesnt mean infinite board, think he means an $n \times n$ board as in beginning of MDBs sketch.
vzn
CC BY-SA 3.0
2013-09-06T21:30:48.230Z
@mhelvens Presumably, the game "computes" in the sense that there is a computable function from inputs to a universal Turing machine (i.e., a description of a machine $M$ and its input $x$) to a position $P$ of some infinite Go variant such that, say, black has a winning strategy from $P$ if, and only if, $M$ accepts $x$.
David Richerby
CC BY-SA 3.0
2013-09-06T22:34:48.150Z
I think @PeterShor nailed it. Go doesn't have a king to checkmate. The game ends when there is nowhere profitable left to play. So on an infinite board the game never ends. And I don't see how you could use any other end game condition, because the score (and therefore the winner) cannot be known until the territorial borders and life/death status of the groups have been settled.
mhelvens
CC BY-SA 3.0
2013-09-06T23:01:50.117Z
Apologies. I should have read the other comments more carefully. Yes, @MarzioDeBiasi's suggestion could work, but the resulting strategies for perfect play would be very... complicated and unfamiliar. A dead group in the corner will suddenly have a chance at life again after board expansion. That means it may be good strategy for the other player to fill in his own territory to capture it outright... unless he knows he will win by a large enough margin, in which case he must not. --- Under these rules, is it still go you're analyzing?
mhelvens
CC BY-SA 3.0
2013-09-07T13:28:41.410Z
Maybe a triple ko can be used to "encode" that the corresponding TM doesn't halt on its input.
Tyson Williams
CC BY-SA 3.0
2013-09-07T13:30:04.527Z
@Tyson: if you're playing on a finite board, even with the ko rule and triple ko, the game can be completely analyzed in PSPACE, which means that it's not Turing complete. Just because a game is able to last forever doesn't mean you can encode the halting problem in it.
Peter Shor 
CC BY-SA 3.0
2013-09-08T08:28:23.583Z
David Eppstein's page [Computational Complexity of Games and Puzzles](http://www.ics.uci.edu/~eppstein/cgt/hard.html) gives a number of references, but I wonder whether any of them is relevant to your specific problem.
J.-E. Pin
CC BY-SA 3.0
2015-03-02T13:27:29.140Z
Another try which makes it more algorithm-like is to have an infinite board with a finite set of stones on it, including a marked group with 2 liberties. Then the input is accepted if there is a winning shisho, i.e. a sequence of ataris leading to the capture of the group. Some gadgets can be used to make the shisho "bounce" in complicated ways. It can diverge (making the computation "loop"), but my guess is the halting problem on this can be solved. It is similar to Langton's ant, but I think the ability to add new stones (other than the shisho) is missing to make it Turing-complete.
Denis
<computability><turing-machines>
Is there a generalization of the GO game that is known to be Turing complete?
Konrad Burnik
# Is there a generalization of the GO game that is known to be Turing complete?

(Asked by: username_0 on 2013-09-06)

Is there a generalization of the GO game that is known to be Turing complete?

If no, do you have some suggestions about reasonable (generalization) rules that can be used to try to prove that it is Turing complete? The obvious one is that the game must be played on an infinite board (positive quadrant). But what about in-game play and end game conditions?

**Tags:** computability, turing-machines
> **Comments:**
> **username_1**: You can also add in the question the reference to the [PSPACE-hardness proof](http://dl.acm.org/citation.cfm?id=322201) by Lichtenstein and Sipser (perhaps it can be used as a starting point)  
> **username_2**: Maybe I'm lacking some background, but in what way is the question of Turing completeness relevant to the game of go? More generally, how can the game be said to *compute* anything?  
> **username_2**: Hm... I guess you could see a given board position as the input and the eventual point-difference, assuming perfect play from both sides, as an encoding of the output. Interesting...  
> **username_3**: If you're playing on a finite board, it can't be Turing-complete. And I'm baffled as to how you decide when a Go game on an infinite board ends.  
> **username_1**: @PeterShor: a possible (reasonable?) generalization can be: start playing on $n \times n$ with an initial configuration that represents the input; the winner scores +1, extend the board to $(n+k) \times (n+k)$ (or $2n \times 2n$ or only horizontally to $2n \times n$ ???) and continue to play without removing old stones, stop the sequence of matches and end the game when the difference of scores is greater than $deltawin$ (or alternatively when a fixed computable function $f(score1,score2) = true$).  
> **username_4**: think author doesnt mean infinite board, think he means an $n \times n$ board as in beginning of MDBs sketch.  
> **username_5**: @mhelvens Presumably, the game "computes" in the sense that there is a computable function from inputs to a universal Turing machine (i.e., a description of a machine $M$ and its input $x$) to a position $P$ of some infinite Go variant such that, say, black has a winning strategy from $P$ if, and only if, $M$ accepts $x$.  
> **username_2**: I think @PeterShor nailed it. Go doesn't have a king to checkmate. The game ends when there is nowhere profitable left to play. So on an infinite board the game never ends. And I don't see how you could use any other end game condition, because the score (and therefore the winner) cannot be known until the territorial borders and life/death status of the groups have been settled.  
> **username_2**: Apologies. I should have read the other comments more carefully. Yes, @MarzioDeBiasi's suggestion could work, but the resulting strategies for perfect play would be very... complicated and unfamiliar. A dead group in the corner will suddenly have a chance at life again after board expansion. That means it may be good strategy for the other player to fill in his own territory to capture it outright... unless he knows he will win by a large enough margin, in which case he must not. --- Under these rules, is it still go you're analyzing?  
> **username_6**: Maybe a triple ko can be used to "encode" that the corresponding TM doesn't halt on its input.  
> **username_3**: @Tyson: if you're playing on a finite board, even with the ko rule and triple ko, the game can be completely analyzed in PSPACE, which means that it's not Turing complete. Just because a game is able to last forever doesn't mean you can encode the halting problem in it.  
> **username_7**: David Eppstein's page [Computational Complexity of Games and Puzzles](http://www.ics.uci.edu/~eppstein/cgt/hard.html) gives a number of references, but I wonder whether any of them is relevant to your specific problem.  
> **username_8**: Another try which makes it more algorithm-like is to have an infinite board with a finite set of stones on it, including a marked group with 2 liberties. Then the input is accepted if there is a winning shisho, i.e. a sequence of ataris leading to the capture of the group. Some gadgets can be used to make the shisho "bounce" in complicated ways. It can diverge (making the computation "loop"), but my guess is the halting problem on this can be solved. It is similar to Langton's ant, but I think the ability to add new stones (other than the shisho) is missing to make it Turing-complete.  

---

## 4 answers

### Answer by username_9 on 2015-04-29. Score: 5

Related: Rengo Kriegspiel, a blindfolded, team variant of Go, is conjectured to be undecidable.

<http://en.wikipedia.org/wiki/Go_variants#Rengo_Kriegspiel>

Robert Hearn's [thesis](http://erikdemaine.org/theses/bhearn.pdf) (and the corresponding [book](http://www.crcpress.com/product/isbn/9781568813226) with Erik Demaine) discuss this problem. They prove other problems undecidable through "TEAM COMPUTATION GAME", which is reduced directly from Turing machine acceptance on empty input (see Theorem 24 on page 70 of the thesis). So it seems to me that such a reduction would imply Rengo Kriegspiel is Turing complete.

On the other hand, their discussion says that this reduction would be very difficult (see page 123). So while this is a potential avenue, it appears that it has been looked into previously.


---

### Answer by username_8 on 2015-04-29. Score: 3

This is a build on my comment, with the idea of using shishos (ladders) as computations. It is merely an attempt to give a computation model that is based on Go, and for which it makes sense to ask whether it is Turing-complete.

We start by fixing some powerful but not Turing-complete computation model that always halts, for instance some typed $\lambda$-calculus, or primitive recursive functions. This is the "cheating" part as we use an external computation model, but it is a weaker one, so hopefully it is the game of Go which will fill the gap and make it Turing-complete.

We consider an infinite goban labeled by $\mathbb Z\times\mathbb Z$.
Now the initial configuration of the goban can be infinite, and is given by an algorithm from our formalism: given coordinates $(i,j)$ the algorithm says whether the intersection $(i,j)$ is empty, occupied by a black stone, or occupied by a white stone.
We fix a maximal size $N$ of the groups in the initial configuration.
This means that given a position, we can always compute the group occupying it and its number of liberties, or answer "invalid configuration".

We also fix a *marked* stone (say black) at coordinate $(0,0)$.
An initial configuration is valid if at the beginning the group of the marked stone has two liberties.

Now we can view this configuration of the goban as the initial configuration of a non-deterministic machine, where a transition consists in playing a white stone at one of the two liberties of the marked group.
At each step, black automatically answers at the other liberty.

The run ends if

* The marked group is captured, in which case the input is accepted
* The marked group acquires more than $2$ liberties, in which case the input is rejected.

The run can also continue forever...

As for non-deterministic Turing machines, the input is accepted if there is an accepting run.

It is easy to simulate this machine with a non-deterministic TM, thanks to the existence of the bound $N$ (which is a parameter of the whole model).

**Conjecture**: For $N$ big enough (probably no more than $10$ to get the necessary gadgets), this model is Turing-complete.


---

### Answer by username_4 on 2015-04-30. Score: -2

here is some evidence/ analysis/ results leaning against your conjecture that a Go generalization might be undecidable (aka "Turing Complete"); at least there does not seem to be a well known or commonly accepted case, and a search returns more results on the idea that its ("natural"?) generalizations are decidable. the generalization considered in this set of papers is PSpace complete. however, there are no "consistent" or "inevitable" ways to generalize games and it is conceivable someone could come up with a variant that is undecidable.

actually most nontrivial games probably can be modified or generalized in some way to have undecidable variants. (a famous simple game/ example along these lines proved "undecidable" by Conway is [Life](http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life).) the following references also point to many other references.

another line of thought might be that no game can be undecidable if it is winnable, ie undecidability works against the idea of games terminating with a winner in a finite number of moves. in other words maybe games are better/ more naturally analyzed as within the (decidable) complexity hierarchy as is typically the case.

* [GO is PSpace hard](http://www.levreyzin.com/presentations/Go.pdf), by Reyzin, talk on result by Lichtenstein, Sipser
* [GO is PSpace hard](http://www.computer.org/csdl/proceedings/focs/1978/5428/00/542800048-abs.html) by Lichetenstein, Sipser
* [Go Endgames Are PSPACE-Hard](http://library.msri.org/books/Book42/files/wolfe.pdf), Wolfe


---

### Answer by username_10 on 2015-04-29. Score: -7

In my patent application - [Turing Complete Sets of Game Components with Divinatory Elements](http://www.faqs.org/patents/app/20150102562) - I describe variants for game rules (including games played on a 19x19 Go board) which add a degree of complexity to games like chess and Go allowing for board positions to simulate linear bounded automata for an arbitrarily long period of time. As mentioned in the comments above, Go on an infinite board would introduce some difficulties as far as determining a game winner, since it is a game with a territorial objective, unlike chess. From my application: "Many other Turing complete game embodiments are possible, but I will give just two more brief descriptive examples to illustrate some other possibilities for adapting games to be played as Turing complete variants and then discuss ramifications. Games like Gomoku (SCARNE, p. 537) and Go (SCARNE, pp. 533-7) which are played on a 19×19 grid with two different colors of pieces are also candidates for Turing complete variants with divinatory elements. In the case of these games, Rogozhin's (2,18) UTM is used. This is also the UTM used by Churchill (2012) as cited in the prior art references. In order to create a game variant of this type, we will use coins for our game pieces. Prepare to play the chosen game variant by sorting large quantities of two different coins--pennies and dimes for example--into piles based on the date on their obverse sides. In this case, dates on the coins will be used as a substitute for colors in the context of the UTM instructions. Colors have been used for UTM instructions in the previously described embodiments, but this embodiment illustrates that another attribute of the game components, in this case a number, may be used. In the most general case, I will refer to this potential for substituting another attribute of the game components in place of colors as a use of a subset of the set of game components. Each player should start with 19 stacks of 19 of their chosen coin. Each stack of pennies and dimes should contain only coins with the same date--let's say, for example, 19 pennies dated 1991, 19 dimes dated 1991, 19 pennies dated 1992, etc. through 19 dimes dated 2009. A coin may only be played in the leftmost column of the board if it has a 1991 date, the next column to the right requires a coin with the 1992 date, etc. through to 2009 in the rightmost column. Play a game of Go or Gomoku as normal except for this rule regarding which pieces may be played where. When the (2,18) UTM is initiated based on pre selected game criteria (in a similar manner to that described in other embodiments) the UTM read/write head will read a heads up coin as being in state 1 and a heads down coin as being in state 2. A coin with the date 1991 will be considered an A coin by the UTM, 1992=B, 1993=C, etc. skipping over the year 2000. Coins are replaced by others with different dates according to the UTM instructions. As far as divinatory elements are concerned, there are 360 degrees in the zodiac and 360 intersections surrounding the central intersection on a Go board, so Sabian symbols (ROCHE) are an obvious fit. For more divinatory aspects of a Go board and game, see "The Religious Dimensions of Go" (SCHNEIDER)." Go game scenarios where a pre agreed UTM analysis of a board position might be useful include boards with [triple kos and boards with long ko fights](http://senseis.xmp.net/?KoPagesTaxonomy).

Is the trade off between adding additional complexity in rules in order to introduce Turing completeness to tabletop games worth the effort? Likely the answer to that question depends on the game and the players, but Magic: the Gathering is an example that in at least some cases the answer to that question is likely to be yes.

> **Comments:**
> **username_11**: Your link only shows what look like "trading cards" without any discussion of Go that I can see. I think this is an advertisement for your patent and not an answer to the question.  
> **username_10**: See the additional embodiments section beginning at paragraph [0135]. I'd quote it here but it won't fit. The gist is to analyse the board using Rogozhin's (2,18) UTM where the standard Go pieces are replaced by pennies and dimes (since they meet the two state requirement, having obverse and reverse sides) with 19 different mint dates (one date for each column on the board). A standard game of Go is played until some pre agreed trigger (triple ko or a ko fight perhaps) in the game mandates a UTM analysis of the board position.  
> **username_11**: Sorry, I don't understand this at all. What you're describing still has a finite number of states, so it can't be Turing complete. More importantly, what do "divinatory elements" and "religious dimensions" have to do with anything?  
> **username_10**: "Divinatory elements" and "religious dimensions" have to do with my patent (see patent title). As I said previously, what is being simulated is linear bounded automata for an arbitrarily long period of time which (if you trust Wikipedia) is generally what we deal with in the real world - http://en.wikipedia.org/wiki/Turing_completeness#Non-mathematical_usage  

---

