1
Puzzles and Challenges / Re: Turing Machine from Dominion Cards and Mechanics
« on: September 04, 2018, 12:43:11 am »
I think the right version of this question is: is there a computable way of translating a program into a dominion game state, such that player 1 has a winning strategy iff the program halts? This is what it would usually mean when we say that a game is Turing complete.
I think it's a good question. Probably the answer is yes, but I don't think that any of the mechanisms suggested so far will work.
You would almost certainly need to make the piles infinite.
One way to approach it is to implement a two-stack automata, a state machine that is allowed to push and pop from either of two stacks (which is Turing complete). For example, one stack could be implemented with the top of the deck and the other can be implemented as a chain of throne rooms / processions. I think this would be incredibly complex and challenging.
I think it's a good question. Probably the answer is yes, but I don't think that any of the mechanisms suggested so far will work.
You would almost certainly need to make the piles infinite.
One way to approach it is to implement a two-stack automata, a state machine that is allowed to push and pop from either of two stacks (which is Turing complete). For example, one stack could be implemented with the top of the deck and the other can be implemented as a chain of throne rooms / processions. I think this would be incredibly complex and challenging.