¿Puede el ajedrez simular una máquina universal de Turing?

16

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?

CAZADOR DE TROLLS
fuente
8
Esta cuestión también está publicada en math.SE , por favor lea el FAQ sobre la publicación cruzada.
Gopi
10
Acabas de publicar esto en math.SE y ya recibiste un puntero útil a un enlace MO, así como una respuesta. Si esto resulta no ser adecuado, puede realizar una publicación cruzada aquí, pero en general preferimos no tener una publicación cruzada simultánea ya que provoca fracturas y repeticiones en el debate. Estoy cerrando por ahora, pero puede marcarlo para reabrirlo si no recibe respuestas satisfactorias en otro lugar (ignore el "motivo del cierre", solo tenemos algunas opciones)
Suresh Venkat
99
Parece bastante improbable, ya que el ajedrez solo tiene un número de piezas en cualquier juego, y una máquina universal de Turing tiene un número ilimitado de bits. Sin embargo, esto no es una prueba.
Peter Shor
1
nortenorte
2
@JE: El interrogador afirmó que las respuestas en otros sitios no eran satisfactorias, por lo que reabrí.
Suresh Venkat

Respuestas:

5

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

domotorp
fuente
4

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.

Marzio De Biasi
fuente
Agradable, aunque la declaración no es demasiado sorprendente.
domotorp
1
@domotorp: Estoy de acuerdo :(, pero la prueba (usando una estructura de primer orden definible en la aritmética de Presburger decidible) es clara.
Marzio De Biasi
@domotorp: ... Estoy tratando de entender esta parte: "... Ahora argumentamos que la colección de tales secuencias de cadenas que surgen de las posiciones es regular, al reconocer con una máquina Turing de cinta múltiple de solo lectura que obedecer los requisitos necesarios ... <requisitos> ... y no hay dos piezas vivas que ocupen el mismo cuadrado ... ". 99.99% Estoy malinterpretando, pero no veo cómo una cadena normal puede incrustar la información de que dos piezas están en cuadrados distintos ...
Marzio De Biasi
así que no estoy realmente familiarizado con este tema, pero ¿no es lo que tienen una máquina T de cinta múltiple? Parece que tienen cada cadena en una cinta separada y luego es fácil de verificar. Supongo que tener dos cintas con la cadena entrelazada sería igual de bueno, si queremos un número limitado de cintas.
domotorp