O xadrez pode simular uma máquina universal de Turing?

16

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?

CAÇADOR DE TROLL
fonte
8
Esta pergunta também foi publicada em math.SE , leia as perguntas frequentes sobre postagem cruzada.
Gopi
10
Você acabou de publicar isso no math.SE e já recebeu um ponteiro útil para um link do MO, além de uma resposta. Se esses resultados não forem adequados, você pode fazer a interseção aqui, mas, em geral, preferimos não ter uma interposição simultânea, pois causa fratura e repetição na discussão. Estou fechando por agora, mas você pode marcá-lo para a reabertura, se você não receber respostas satisfatórias em outros lugares (por favor ignore a "razão para o fechamento" - só temos algumas escolhas)
Suresh Venkat
9
Parece bastante improvável, pois o xadrez possui apenas um número de peças em um jogo e uma máquina de Turing universal possui um número ilimitado de bits. No entanto, isso não é uma prova.
quer
11
@ Tayfun Pay: Você está "resolvendo" um problema diferente. A versão EXP-C do xadrez possui peças específicas atribuídas ao tabuleiro, dependendo do valor da largura do tabuleiro . O número de torres etc. cresce como uma fração de . A pergunta feita aqui é (a) tabuleiro infinito e (b) qualquer número de peças, em qualquer proporção uma da outra. nn
Aaron Sterling
2
@JE: O questionador afirmou que as respostas em outros sites eram insatisfatórias, então reabri.
Suresh Venkat

Respostas:

5

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

domotorp
fonte
4

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.

Marzio De Biasi
fonte
Bom, embora a afirmação não seja muito surpreendente.
domotorp
11
@domotorp: Eu concorda :(, mas a prova (usando uma estrutura definível de primeira ordem na aritmética Presburger decidíveis) é limpo.
Marzio De Biasi
@domotorp: ... Estou tentando entender esta parte: "... Agora argumentamos que a coleta de tais seqüências de strings decorrentes de posições é regular, reconhecendo com uma máquina de Turing multi-fita somente leitura que eles obedeça aos requisitos necessários ... <requisitos> ... e não há duas peças vivas ocupando o mesmo quadrado ... ". 99,99% eu estou interpretando mal, mas eu não vejo como uma lata seqüência regular incorporar as informações de que duas peças estão em praças distintas ...
Marzio De Biasi
então eu não estou realmente familiarizado com esse tópico, mas não é o que eles têm com uma máquina T com várias fitas? Parece que eles têm cada corda em uma fita separada e é fácil verificar. Eu acho que ter duas fitas com a corda intercalada seria tão bom, se quisermos um número limitado de fitas.
Domotorp # 7/13