Existe uma generalização do jogo GO que se sabe que Turing está completo?

Existe uma generalização do jogo GO que se sabe que Turing está completo?

Se não, você tem algumas sugestões sobre regras razoáveis ​​(generalização) que podem ser usadas para tentar provar que Turing está completo? O óbvio é que o jogo deve ser jogado em um tabuleiro infinito (quadrante positivo). Mas e as condições de jogo e final do jogo?

Relacionado: Rengo Kriegspiel, uma variante vendada da equipe de Go, é considerada indecidível.

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

A tese de Robert Hearn (e o livro correspondente com Erik Demaine) discutem esse problema. Eles provam outros problemas indecidíveis através do "JOGO DE COMPUTAÇÃO DE EQUIPE", que é reduzido diretamente da aceitação da máquina de Turing em entradas vazias (consulte o Teorema 24 na página 70 da tese). Parece-me, portanto, que essa redução implicaria que Rengo Kriegspiel é Turing completo.

Por outro lado, a discussão deles diz que essa redução seria muito difícil (veja a página 123). Portanto, embora essa seja uma avenida potencial, parece que ela foi analisada anteriormente.

Esta é uma compilação no meu comentário, com a ideia de usar shishos (escadas) como cálculos. É apenas uma tentativa de fornecer um modelo de computação baseado em Go e para o qual faz sentido perguntar se ele é completo em Turing.

$\lambda$

$\mathbb Z\times\mathbb Z$$(i,j)$$(i,j)$$N$

$(0,0)$

Agora podemos ver essa configuração do goban como a configuração inicial de uma máquina não determinística, onde uma transição consiste em jogar uma pedra branca em uma das duas liberdades do grupo marcado. A cada passo, o preto responde automaticamente na outra liberdade.

A corrida termina se

• O grupo marcado é capturado, caso em que a entrada é aceita
• $2$

A corrida também pode continuar para sempre ...

Quanto às máquinas de Turing não determinísticas, a entrada é aceita se houver uma execução de aceitação.

$N$

$N$$10$

aqui estão algumas evidências / análises / resultados apoiados na sua conjectura de que uma generalização Go pode ser indecidível (também conhecida como "Turing Complete"); pelo menos não parece haver um caso conhecido ou comumente aceito, e uma pesquisa retorna mais resultados com a idéia de que suas generalizações ("naturais"?) são decidíveis. a generalização considerada neste conjunto de papéis é PSpace completa. no entanto, não existem maneiras "consistentes" ou "inevitáveis" de generalizar jogos e é concebível que alguém possa inventar uma variante indecidível.

na verdade, a maioria dos jogos não triviais provavelmente pode ser modificada ou generalizada de alguma forma para ter variantes indecidíveis. (um famoso jogo / exemplo simples nesse sentido se mostrou "indecidível" por Conway é Life .) As referências a seguir também apontam para muitas outras referências.

outra linha de pensamento pode ser a de que nenhum jogo pode ser indecidível se for vencível, ou seja, a indecidibilidade trabalha contra a idéia de jogos terminando com um vencedor em um número finito de jogadas. em outras palavras, talvez os jogos sejam melhor / mais naturalmente analisados ​​como dentro da hierarquia de complexidade (decidível), como é normalmente o caso.

• GO é difícil para o PSpace , de Reyzin, sobre resultado de Lichtenstein, Sipser
• GO é PSpace rígido por Lichetenstein, Sipser
• Os jogos finais são difíceis para PSPACE , Wolfe

No meu pedido de patente - Conjuntos completos de Turing de componentes de jogos com elementos divinatórios- Descrevo variantes de regras de jogo (incluindo jogos jogados em um tabuleiro de 19x19) que adicionam um grau de complexidade a jogos como xadrez e Go, permitindo que as posições do tabuleiro simulem autômatos limitados lineares por um período arbitrariamente longo. Como mencionado nos comentários acima, Ir para um tabuleiro infinito traria algumas dificuldades na determinação de um vencedor do jogo, pois é um jogo com um objetivo territorial, diferentemente do xadrez. No meu aplicativo: "Muitas outras formas de realização completas de jogos de Turing são possíveis, mas darei apenas mais dois exemplos descritivos para ilustrar algumas outras possibilidades de adaptar jogos a serem jogados como variantes completas de Turing e, em seguida, discutir ramificações. Jogos como Gomoku (SCARNE, 537) e Go (SCARNE, pp. 533-7), que são jogadas em uma grade 19 × 19 com duas cores diferentes de peças, também são candidatas a variantes completas de Turing com elementos divinatórios. No caso desses jogos, o UTM de Rogozhin (2,18) é usado. Este também é o UTM usado por Churchill (2012), conforme citado nas referências da arte anterior. Para criar uma variante de jogo desse tipo, usaremos moedas para as peças do jogo. Prepare-se para jogar a variante de jogo escolhida, classificando grandes quantidades de duas moedas diferentes - moedas de um centavo e moedas de dez centavos, por exemplo - em pilhas com base na data em seus lados anversos. Nesse caso, as datas nas moedas serão usadas como substituto das cores no contexto das instruções da UTM. As cores foram usadas para instruções UTM nas modalidades descritas anteriormente, mas essa modalidade ilustra que outro atributo dos componentes do jogo, neste caso, um número, pode ser usado. No caso mais geral, vou me referir a esse potencial para substituir outro atributo dos componentes do jogo no lugar das cores como uso de um subconjunto do conjunto de componentes do jogo. Cada jogador deve começar com 19 pilhas de 19 da moeda escolhida. Cada pilha de moedas e moedas de um centavo deve conter apenas moedas com a mesma data - digamos, por exemplo, 19 moedas de um centavo de 1991, 19 moedas de um centavo de 1991, 19 moedas de um centavo de 1992 etc. etc. até 19 moedas de um centavo de 2009. Uma moeda só pode ser jogada na coluna mais à esquerda do tabuleiro, se houver uma data de 1991, a próxima coluna à direita exige uma moeda com a data de 1992 etc. até 2009 na coluna da direita. Jogue um jogo de Go ou Gomoku normalmente, exceto por esta regra sobre quais peças podem ser jogadas onde. Quando o (2, 18) O UTM é iniciado com base em critérios de jogo pré-selecionados (de maneira semelhante à descrita em outras modalidades) a cabeça de leitura / gravação do UTM lerá uma moeda heads-up como estando no estado 1 e uma moeda heads-down como estando no estado 2 Uma moeda com a data de 1991 será considerada uma moeda A pela UTM, 1992 = B, 1993 = C, etc. pulando ao longo do ano 2000. As moedas são substituídas por outras com datas diferentes, de acordo com as instruções da UTM. No que diz respeito aos elementos divinatórios, existem 360 graus no zodíaco e 360 ​​interseções em torno da interseção central em uma placa Go, então os símbolos sabianos (ROCHE) são um ajuste óbvio. Para aspectos mais divinatórios de um tabuleiro e jogo de Go, consulte "As dimensões religiosas de Go" (SCHNEIDER). "Cenários de jogos de Go em que uma análise UTM pré-acordada de uma posição de tabuleiro pode ser útil, incluindo tabuleiros comkos triplos e pranchas com longas lutas de ko .

A troca entre adicionar complexidade adicional às regras para introduzir a integridade de Turing nos jogos de mesa vale o esforço? Provavelmente, a resposta para essa pergunta depende do jogo e dos jogadores, mas Magic: the Gathering é um exemplo de que, pelo menos em alguns casos, a resposta a essa pergunta provavelmente é sim.