Ich bin auf der Suche nach einer endgültigen Antwort auf die Titelfrage.
Gibt es eine Reihe von Regeln, die ein Programm in eine Konfiguration von endlichen Stücken auf einem unendlichen Brett umwandeln, sodass, wenn Schwarz und Weiß nur legale Züge spielen, das Spiel in endlicher Zeit endet, wenn das Programm anhält?
Die Regeln sind die gleichen wie beim gewöhnlichen Schach, abzüglich der 50-Züge-Regel, des Austauschs und der Rochade.
Und was ist die minimale Anzahl verschiedener Arten von Steinen (dh das einfachste Spiel), die benötigt werden, damit ein schachähnliches Spiel vollständig ist? (Jede Art von Stück mit einer Reihe von erlaubten Zügen, die unter Übersetzungen unveränderlich sind).
Gibt es ein Stück, das wir dem Spiel hinzufügen können, um zu beweisen, dass es vollständig ist?
Antworten:
Ich denke auch, dass eine sehr ähnliche Frage schon einmal gestellt wurde, ich denke zuerst hier: /mathpro/27967/decidability-of-chess-on-an-infinite-board/63684 Hier ist mein aktualisiertes und geänderte Meinung.
Ich denke, das Problem ist nicht vollständig gelöst, aber die Antwort lautet mit ziemlicher Sicherheit Ja. Ich habe keinen Beweis für Schach, da ich nicht in der Lage bin, bestimmte Konfigurationen zu entwerfen, aber ich denke, dass sie existieren müssen. Und selbst wenn sie es nicht tun, tun sie es für ein schachartiges Spiel, was zeigt, dass die Versuche, die Entscheidbarkeit zu beweisen, falsch sein sollten. Später wurde mir klar, dass es hier ein sehr ähnliches Argument gibt: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006, aber mein Beweis zeigt, dass tatsächlich zwei Zähler ausreichen und vielleicht meins ist detaillierter.
Die Reduzierung beruht auf dem Begriff einer Stapelmaschine. Eine Stapelmaschine mit nur zwei Stapeln, die ein Stapelalphabet mit nur einem Buchstaben verwendet, kann jede Turing-Maschine simulieren. (Einige Leute würden diesen deterministischen endlichen Automaten mit zwei Zählern bezeichnen.) Unser Ziel wäre es also, eine solche Maschine mit einer Schachposition zu simulieren. Dafür sehe ich zwei Möglichkeiten.
i) Erstellen Sie zwei separate Konfigurationen, sodass sowohl ein Startteil als auch ein bewegliches Teil geändert werden können (um den Status zu speichern). Auch die beweglichen Teile wären miteinander verbunden, z. von Türmen, die sich beim Loslassen schachmatt setzen könnten. Wenn einer der Zustände 1 ist, muss der andere k bewegen und so weiter.
ii) Erstellen Sie eine einzelne Konfiguration, die sich je nach Status horizontal und vertikal bewegt. Platzieren Sie außerdem einen Turm bei (0,0), der sich niemals bewegen würde, aber gewährleisten könnte, dass die Konfiguration "erkennen" kann, wenn sie zu einem leeren Zähler zurückkehrt.
Es bleibt also nichts anderes zu tun, als solche Konfigurationen zu entwerfen, die meiner Meinung nach mit etwas Aufwand und Schachkenntnissen möglich sein sollten. Beachten Sie auch, dass die Konstruktion in beiden Fällen ein Stück verwendet, dessen Reichweite nicht begrenzt ist. Ob dies wirklich notwendig ist? Als ersten Schritt schlug ich vor, eine der Collatz-Vermutung äquivalente Position anzugeben: /mathpro/64966/is-there-a-chess-position-äquivalent-zur-Kollatz-Vermutung
quelle
Gestern habe ich gegoogelt, um den Status dieses Problems zu überprüfen, und ich habe das neue (2012) Ergebnis gefunden:
Dan Brumleve, Joel David Hamkins und Philipp Schlicht, Das Mitspielerproblem des unendlichen Schachs ist entscheidbar (2012)
Also kann das Mate-in-n-Problem des unendlichen Schachs nicht vollständig sein.
Die Entscheidbarkeit von unendlichem Schach ohne Beschränkung der Anzahl von Zügen für einen Partner scheint noch offen zu sein.
quelle