Estoy buscando obtener una respuesta definitiva a la pregunta del título.
¿Existe un conjunto de reglas que traduzca cualquier programa en una configuración de piezas finitas en un tablero infinito, de modo que si el blanco y negro juega solo movimientos legales, el juego termina en un tiempo finito si el programa se detiene?
Las reglas son las mismas que las del ajedrez ordinario menos la regla de 50 movimientos, los intercambios y el enroque.
¿Y cuál es el número mínimo de diferentes tipos de piezas (es decir, el juego más simple) que se necesita para que un juego de ajedrez sea completo? (Cada tipo de pieza tiene un conjunto de movimientos permitidos que es invariable bajo las traducciones).
¿Hay alguna pieza que podamos agregar al juego para demostrar que está completo?
fuente
Respuestas:
También creo que se ha hecho una pregunta muy similar antes, primero pienso aquí: /mathpro/27967/decidability-of-chess-on-an-infinite-board/63684 Aquí está mi actualización y Opinión modificada.
Creo que el problema no se resuelve por completo, pero la respuesta es casi segura que sí. No tengo una prueba para el ajedrez, ya que me falta la capacidad de diseñar ciertas configuraciones, pero creo que deben existir. E incluso si no lo hacen, para un juego similar al ajedrez, ciertamente lo hacen, lo que demuestra que los intentos de demostrar la capacidad de decisión deberían ser incorrectos. Más tarde me di cuenta de que hay un argumento muy similar al mío aquí: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006, pero mi prueba muestra que, de hecho, dos contadores son suficientes y tal vez La mía es más detallada.
La reducción se basa en la noción de una máquina apiladora. Una máquina de pila con solo dos pilas que usa un alfabeto de pila de solo una letra puede simular cualquier máquina de Turing. (Algunas personas llamarían a este autómata finito determinista con dos contadores). Entonces, nuestro objetivo sería simular cualquier máquina con una posición de ajedrez. Puedo ver dos formas para esto.
i, Construya dos configuraciones separadas, de modo que ambas tengan una parte inicial y una parte móvil que pueda cambiar (para almacenar el estado). Además, las partes móviles estarían conectadas, por ejemplo. por torres, lo que podría hacer jaque mate, si se libera, por eso si uno declara movimientos 1, el otro tiene que mover k, y así sucesivamente.
ii, Construya una configuración única, que dependiendo de su estado, se mueva l horizontalmente y -k verticalmente. Además, coloque una torre en (0,0) que nunca se movería pero podría garantizar que la configuración pueda "detectar" cuando vuelva a un contador vacío.
Entonces, todo lo que queda por hacer es diseñar tales configuraciones, lo que supongo que debería ser posible con un poco de esfuerzo y conocimiento del ajedrez. Además, tenga en cuenta que en ambos casos la construcción utiliza una pieza cuyo rango no está limitado, me pregunto si esto es realmente necesario. Como primer paso, propuse dar una posición equivalente a la conjetura de Collatz: /mathpro/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture
fuente
Ayer busqué en Google para verificar el estado de este problema y encontré este nuevo resultado (2012):
Dan Brumleve, Joel David Hamkins y Philipp Schlicht, El problema del compañero de ajedrez infinito es decidible (2012)
Entonces, el problema de compañero en n del ajedrez infinito no puede ser Turing completo.
La capacidad de decisión del ajedrez infinito sin restricciones en el número de movimientos para un compañero parece aún abierta.
fuente