Czy szachy mogą symulować uniwersalną maszynę Turinga?

Szukam konkretnej odpowiedzi na pytanie tytułowe.

Czy istnieje zbiór zasad, które przekładają dowolny program na konfigurację skończonych elementów na nieskończonej planszy, tak że jeśli czarno-biały gra tylko legalne ruchy, gra kończy się w skończonym czasie, jeśli program się zatrzymuje?

Zasady są takie same jak zwykłe szachy minus 50 zasada ruchu, wymiana i roszowanie.

Jaka jest minimalna liczba różnych rodzajów elementów (tj. Najprostsza gra), która jest potrzebna, aby gra w szachy była kompletna? (Każdy rodzaj elementu posiadającego zestaw dozwolonych ruchów, który jest niezmienny w tłumaczeniach).

Czy jest jakiś element, który możemy dodać do gry, aby udowodnić, że jest ukończony?

computability turing-machines board-games halting-problem recreational TROLLHUNTER
źródło

To pytanie jest także opublikowane na stronie matemat.SE. Przeczytaj często zadawane pytania na temat krzyżowania postów.

Gopi,

Właśnie opublikowałeś to na math.SE i już otrzymałeś pomocny wskaźnik do linku MO, a także odpowiedź. Jeśli okaże się, że nie są odpowiednie, możesz tutaj stosować krzyżowanie, ale generalnie wolimy nie mieć jednoczesnego krzyżowania, ponieważ powoduje to pękanie i powtarzanie dyskusji. Na razie się zamykam, ale możesz zgłosić to do ponownego otwarcia, jeśli nie otrzymasz zadowalających odpowiedzi w innym miejscu (zignoruj „powód zamknięcia” - mamy tylko kilka opcji)

Suresh Venkat,

Wydaje się to dość mało prawdopodobne, ponieważ szachy mają tylko niewielką liczbę elementów w każdej grze, a uniwersalna maszyna Turinga ma nieograniczoną liczbę bitów. Nie jest to jednak dowód.

Peter Shor,

@Tayfun Pay: „Rozwiązujesz” inny problem. Wersja szachowa EXP-C ma określone elementy przypisane do planszy, w zależności od wartości szerokości planszy

. Liczba wież, itp., Rośnie jako ułamek

. Pytanie, które tu postawiono, to (a) nieskończona tablica i (b) dowolna liczba elementów, w proporcji do siebie.

n

$n$

n

$n$

Aaron Sterling

@JE: Pytający stwierdził, że odpowiedzi na innych stronach są niezadowalające, więc otworzyłem ponownie.

Suresh Venkat

Odpowiedzi:

Myślę też, że wcześniej zadano bardzo podobne pytanie, najpierw myślę tutaj: /mathpro/27967/decidability-of-chess-on-an-infinite-board/63684 Oto moja aktualizacja i zmodyfikowana opinia.

Myślę, że problem nie został całkowicie rozwiązany, ale odpowiedź jest prawie na pewno tak. Nie mam dowodu na grę w szachy, ponieważ nie jestem w stanie zaprojektować pewnych konfiguracji, ale myślę, że muszą istnieć. A nawet jeśli nie, w przypadku niektórych szachowych gier z pewnością robią to, co pokazuje, że próby udowodnienia rozstrzygalności powinny być nieprawidłowe. Później zdałem sobie sprawę, że istnieje bardzo podobny argument do mojego tutaj: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006, ale mój dowód pokazuje, że w rzeczywistości dwa liczniki są wystarczające i może mój jest bardziej szczegółowy.

Redukcja polega na koncepcji maszyny do układania w stosy. Maszyna składająca się tylko z dwóch stosów wykorzystująca alfabet stosu składający się tylko z jednej litery może symulować dowolną maszynę Turinga. (Niektórzy nazywają ten deterministyczny automat skończony dwoma licznikami.) Naszym celem jest więc symulacja dowolnej takiej maszyny z pozycją szachową. Widzę na to dwa sposoby.

i. Zbuduj dwie osobne konfiguracje, tak aby obie miały część początkową i część ruchomą, które można zmienić (w celu zapisania stanu). Również ruchome części byłyby połączone, np. przez wieże, które mogą zostać zamatowane, jeśli zostaną zwolnione, dlatego jeśli jeden stan porusza się 1, drugi musi przesunąć k i tak dalej.

ii. Zbuduj pojedynczą konfigurację, która w zależności od stanu przesunie l poziomo i -k pionowo. Ponadto ustaw wieżę na (0,0), która nigdy się nie poruszy, ale może zagwarantować, że konfiguracja „wyczuje”, gdy wróci do pustego licznika.

Pozostało mi więc zaprojektować takie konfiguracje, które, jak sądzę, powinny być możliwe przy odrobinie wysiłku i wiedzy o szachach. Zauważ też, że w obu przypadkach konstrukcja wykorzystuje element, którego zasięg nie jest ograniczony, zastanawiam się, czy jest to naprawdę konieczne. Jako pierwszy krok zaproponowałem podanie pozycji równoważnej hipotezie Collatza: /mathpro/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture

domotorp
źródło

Wczoraj przeszukałem go, by sprawdzić status tego problemu, i znalazłem nowy (2012) wynik:

Dan Brumleve, Joel David Hamkins i Philipp Schlicht, Problem matematyczny nieskończonych szachów jest rozstrzygalny (2012)

Tak więc problem łączenia nieskończonych szachów nie może być kompletny.

Rozstrzygalność nieskończonych szachów bez ograniczeń liczby ruchów partnera wydaje się wciąż otwarta.

Marzio De Biasi
źródło

To miłe, choć oświadczenie nie jest zbyt zaskakujące.

domotorp

@domotorp: Zgadzam się :(, ale dowód (przy użyciu struktury pierwszego rzędu definiowalnej w rozstrzygającej arytmetyki Presburgera) jest zgrabny.

Marzio De Biasi,

@domotorp: ... Staram się zrozumieć tę część: „... Twierdzimy teraz, że zbiór takich sekwencji ciągów powstających z pozycji jest regularny, rozpoznając za pomocą maszyny Turinga z wieloma taśmami tylko do odczytu, że przestrzegać niezbędnych wymagań ... <wymagania> ... i żadne dwa żywe elementy nie zajmują tego samego kwadratu ... ". 99,99% Błędnie to interpretuję, ale nie rozumiem, jak zwykły ciąg może osadzić informację, że dwa kawałki znajdują się na odrębnych kwadratach ...

Marzio De Biasi

więc nie jestem do końca zaznajomiony z tym tematem, ale czy nie jest tak, że mają maszynę T z wieloma taśmami? Wygląda na to, że mają one każdy ciąg na osobnej taśmie, a następnie można to łatwo sprawdzić. Wydaje mi się, że posiadanie dwóch taśm z przeplecionym łańcuchem byłoby równie dobre, gdybyśmy chcieli ograniczonej liczby taśm.

domotorp