Estou procurando obter uma resposta definitiva para a pergunta do título.
Existe um conjunto de regras que traduz qualquer programa em uma configuração de peças finitas em um tabuleiro infinito, de modo que, se preto e branco executam apenas movimentos legais, o jogo termina em um tempo finito se o programa parar?
As regras são as mesmas do xadrez comum, menos a regra dos 50 movimentos, trocas e rolagem.
E qual é o número mínimo de tipos diferentes de peças (ou seja, o jogo mais simples) que é necessário para que um jogo semelhante ao xadrez seja completo? (Cada tipo de peça com um conjunto de movimentos permitidos que é invariável nas traduções).
Existe alguma peça que possamos adicionar ao jogo para provar que ele está completo?
computability
turing-machines
board-games
halting-problem
recreational
CAÇADOR DE TROLL
fonte
fonte
Respostas:
Também acho que uma pergunta muito semelhante já foi feita antes, acho que primeiro aqui: /mathpro/27967/decidability-of-chess-on-an-infinite-board/63684 Aqui está o meu artigo atualizado e opinião modificada.
Eu acho que o problema não está resolvido completamente, mas a resposta é quase certamente sim. Não tenho prova de xadrez, pois não tenho a capacidade de projetar certas configurações, mas acho que elas devem existir. E mesmo que não o façam, para algum jogo semelhante ao xadrez, eles certamente fazem o que mostra que as tentativas de provar a decidibilidade devem estar incorretas. Mais tarde, percebi que existe um argumento muito semelhante ao meu aqui: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006, mas minha prova mostra que, de fato, dois contadores são suficientes e talvez o meu é mais detalhado.
A redução depende da noção de uma máquina de empilhar. Uma máquina de pilha com apenas duas pilhas usando um alfabeto de pilha de apenas uma letra pode simular qualquer máquina de Turing. (Algumas pessoas chamariam isso de autômato finito determinístico com dois contadores.) Portanto, nosso objetivo seria simular qualquer máquina desse tipo com uma posição de xadrez. Eu posso ver duas maneiras para isso.
i, Crie duas configurações separadas, de modo que ambas tenham uma parte inicial e uma parte móvel que possam ser alteradas (para armazenar o estado). Além disso, as partes móveis seriam conectadas, por exemplo. pelas torres, que poderiam dar xeque-mate, se liberadas, e é por isso que se um indica o movimento 1, o outro tem que mover k e assim por diante.
ii, Construa uma configuração única que, dependendo de seu estado, mova l horizontalmente e -k verticalmente. Além disso, coloque uma torre em (0,0) que nunca se moveria, mas poderia garantir que a configuração possa "detectar" quando voltar a um contador vazio.
Portanto, tudo o que precisamos fazer é projetar essas configurações, o que acho que deve ser possível com algum esforço e conhecimento do xadrez. Além disso, observe que em ambos os casos a construção usa uma peça cujo alcance não é limitado, eu me pergunto se isso é realmente necessário. Como primeiro passo, propus dar uma posição equivalente à conjectura de Collatz: /mathpro/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture
fonte
Ontem, procurei no Google o status desse problema e encontrei este novo resultado (2012):
Dan Brumleve, Joel David Hamkins e Philipp Schlicht, O problema companheiro do xadrez infinito é decidível (2012)
Portanto, o problema do xadrez infinito não pode ser Turing completo.
A decidibilidade do xadrez infinito sem restrições no número de jogadas para um parceiro ainda parece aberta.
fonte