Saya mencari jawaban pasti untuk pertanyaan judul.
Apakah ada seperangkat aturan yang menerjemahkan program apa pun ke dalam konfigurasi potongan terbatas di papan infinite, sehingga jika hitam dan putih hanya memainkan gerakan hukum, permainan berakhir pada waktu terbatas jika program berhenti?
Aturannya sama dengan catur biasa minus 50 aturan gerak, pertukaran, dan kasting.
Dan berapa jumlah minimum dari berbagai jenis keping (yaitu gim paling sederhana) yang diperlukan untuk gim seperti catur agar bisa menyelesaikan-turing? (Setiap jenis karya memiliki satu set gerakan yang diizinkan yang tidak berubah di bawah terjemahan).
Apakah ada bagian yang bisa kita tambahkan ke game untuk membuktikannya selesai?
Jawaban:
Saya juga berpikir bahwa pertanyaan yang sangat mirip telah ditanyakan sebelumnya, saya pikir pertama di sini: /mathpro/27967/decidability-of-chess-on-an-infinite-board/63684 Berikut adalah saya diperbarui dan opini yang dimodifikasi.
Saya pikir masalahnya belum diselesaikan sepenuhnya, tetapi jawabannya hampir pasti ya. Saya tidak punya bukti untuk catur, karena saya tidak memiliki kemampuan untuk merancang konfigurasi tertentu, tetapi saya pikir mereka harus ada. Dan bahkan jika mereka tidak melakukannya, untuk beberapa permainan seperti catur mereka pasti melakukan yang menunjukkan bahwa upaya untuk membuktikan kepatutan harus salah. Kemudian saya menyadari bahwa ada argumen yang sangat mirip dengan saya di sini: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006 tetapi bukti saya menunjukkan bahwa sebenarnya dua penghitung sudah cukup dan mungkin punyaku lebih detail.
Pengurangan bergantung pada gagasan mesin stack. Mesin tumpukan dengan hanya dua tumpukan menggunakan tumpukan alfabet hanya satu huruf dapat mensimulasikan mesin Turing. (Beberapa orang akan menyebutnya robot yang terbatas deterministik ini dengan dua counter.) Jadi tujuan kami adalah untuk mensimulasikan setiap mesin tersebut dengan posisi catur. Saya bisa melihat dua cara untuk ini.
i, Bangun dua konfigurasi terpisah, sehingga keduanya memiliki bagian awal dan bagian bergerak yang dapat berubah (untuk menyimpan keadaan). Juga, bagian yang bergerak akan dihubungkan, misalnya. oleh benteng, yang bisa sekakmat, jika dilepaskan, jadi ini adalah mengapa jika satu negara bergerak 1, yang lain harus bergerak k, dan seterusnya.
ii, Membangun satu konfigurasi, yang tergantung pada kondisinya, bergerak l secara horizontal dan -k secara vertikal. Juga, tempatkan benteng di (0,0) yang tidak akan pernah bergerak tetapi bisa menjamin bahwa konfigurasi dapat "merasakan" ketika kembali ke penghitung kosong.
Jadi yang tersisa untuk dilakukan adalah merancang konfigurasi seperti itu, yang saya kira harus dimungkinkan dengan sedikit usaha dan pengetahuan catur. Juga, perhatikan bahwa dalam kedua kasus konstruksi menggunakan sepotong yang rentang tidak dibatasi, saya bertanya-tanya apakah ini benar-benar diperlukan. Sebagai langkah pertama, saya mengusulkan untuk memberikan posisi yang setara dengan dugaan Collatz: /mathpro/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture
sumber
Kemarin saya googled sekitar untuk memeriksa status masalah ini dan saya menemukan hasil baru (2012) ini:
Dan Brumleve, Joel David Hamkins dan Philipp Schlicht, Masalah mate-in-n catur tak terbatas dapat ditentukan (2012)
Jadi masalah mate-in-n catur tidak terbatas tidak bisa diselesaikan Turing.
Desidabilitas catur tanpa batas tanpa batasan jumlah gerakan untuk pasangan tampaknya masih terbuka.
sumber