Apakah Magic: the Gathering Turing lengkap?

Pertanyaan yang sangat spesifik, saya sadar, dan saya ragu itu akan dijawab oleh siapa pun yang belum terbiasa dengan aturan Sihir. Diposting silang ke Draw3Cards . Berikut adalah aturan komprehensif untuk game Magic: the Gathering . Lihat pertanyaan ini untuk daftar semua Kartu Ajaib. Pertanyaan saya adalah - apakah game Turing Lengkap?

Untuk detail lebih lanjut, silakan lihat posting di Draw3Cards .

Alex Churchill (@AlexC) telah memposting solusi yang tidak memerlukan kerja sama antara para pemain, melainkan memodelkan eksekusi lengkap dari mesin Turing universal dengan dua negara dan 18 simbol simbol. Untuk detailnya, lihat https://www.toothycat.net/~hologram/Turing/ [ arsip ].

Ok, saya punya solusi yang menghindari masalah burn mana yang saya temui. Ini semacam peretasan, karena saya perlu membuat asumsi bahwa pemain dapat mengidentifikasi tanah tertentu, yang saya pikir tidak diatur dalam aturan. Dalam praktiknya inilah masalahnya, karena mereka dapat diatur dalam garis berdasarkan urutan permainan mereka.

Pertama, uraian lengkap masalah dari situs Draw3Cards:

Jawaban positif akan terdiri dari komponen-komponen ini:

1. Fungsi yang dapat dihitung dari Turing Machines hingga Magic decks (di mana urutan perpustakaan penting)
2. Dua strategi deterministik & komputasi yang dapat ditentukan dengan baik untuk memainkan Magic (yang tidak bergantung pada deck). Sebut mereka Strategi TS (Strategi Turing) dan Strategi IS (Strategi Input).
3. Cara yang dapat dihitung untuk mengkodekan string apa pun dari nol dan yang sebagai dek Input Magic. Salah satu caranya adalah dengan mengambil nomor Gödel dari string dan meletakkan sebanyak mungkin pulau di dek Input.

Kondisi tambahan yang harus dipenuhi adalah ini: Diberikan Turing Machines TM, mari kita perhatikan hasil dari permainan Sihir antara strategi TS bermain dengan deck fM (TM) terhadap strategi TI bermain dengan deck fI (I), ketika perpustakaan sedang tidak dikocok sebelum pertandingan dimulai. Game ini harus dimenangkan oleh pemain pertama jika dan hanya jika TM (I) = true.

Jadi inilah idenya. Kami memiliki 2 pemain, A dan B. B akan memasok input, sementara A akan langsung mengimplementasikan mesin Turing. Dek akan terdiri hampir seluruhnya dari tanah, tetapi juga kartu Array Batu Permata untuk membatalkan pembakaran mana. A akan memiliki 3 jenis tanah: Pulau, Gunung, dan Hutan. Ide dasarnya adalah menggunakan lahan yang disadap untuk mewakili 1 dan lahan yang belum dimanfaatkan untuk mewakili 0. Pulau akan digunakan untuk mewakili keadaan pita, Pegunungan untuk mengindeks posisi saat ini di sepanjang pita dan Hutan untuk mewakili keadaan internal 24 negara 2 simbol mesin Turing (saya percaya ada yang universal karena Rogozhin).

$2^5 = 32 > 24$$2^{m+1}$

$2^5 = 32 > 24$$2^{m+1}$

Strategi: A dan B memainkan satu tanah secara bergantian sesuai urutan pengambilannya. Ketika masing-masing telah menggambar 4 hutan mereka memainkan Artefak Batu Permata. Catatan A berjalan lebih dulu, jadi sudah memiliki Pulau ketika B menggambar memainkan kartu input pertamanya.

A dan B terus menempatkan kartu mereka dalam urutan sampai B telah kehabisan Dataran dan Rawa-rawa mereka dan memainkan Pulau pertama mereka. Pada perjalanan berikutnya, A untuk semua yang saya sentuh Pulau itf jika BS dan Input Land adalah rawa. A menginisialisasi mesin turingnya dengan mengetuk Hutan dan Gunung pertamanya. Jika dia telah mengetuk sejumlah kartu aneh, dia mengetuk forrest tambahannya, dan menggunakan semua mana ini untuk menambahkan token ke Gemstone Array. Dari sini, permainan dilanjutkan sebagai berikut: B menggunakan giliran mereka untuk hanya mencerminkan keadaan mana A. B mengetuknya Input Tanah jika Pulau ituk disadap. Demikian pula B mengetuk Hutan ke-5 (Gunung) jika Hutan ke-A (Gunung) disadap. Sebagai A selalu mengetuk jumlah kartu genap, begitu juga B, dan mana digunakan untuk menambahkan token ke Gemstone Array.

Pada giliran A, semua mana A menjadi tidak tersentuh, jadi A melihat keadaan mana B, mewakili keadaan mana A pada giliran sebelumnya. A menerapkan aturan transisi sesuai dengan mesin universal (24,2) ke kondisi B untuk mendapatkan status barunya.

Mainkan hasil dengan cara ini sampai mesin turing berhenti. Pada titik ini, A menempatkan gunung-gunungnya ke dalam status "selesai" yang dilindungi (semua yang belum dimanfaatkan). Jika mesin Turing berhenti dalam keadaan menerima, B menyalin keadaan pegunungan A, tetapi mengetuk semua tanah yang tersisa dengan mengabaikan susunan Batu Permata, sehingga memulai proses bunuh diri dengan cara membakar. Pada gilirannya A, jika pegunungan B dalam keadaan "selesai", dan semua tanah B lainnya disadap, A tidak melakukan apa-apa (perhatikan bahwa pegunungannya secara otomatis dalam keadaan "selesai"). Jika pegunungan A berada dalam kondisi selesai, tetapi tidak ada yang disadap, B terus bunuh diri dengan cara membakar. Ini diulangi sampai B mati.

Namun, jika mesin selesai dalam kondisi tolak, B membiarkan semua kartunya tidak tersentuh. Jika semua kartu B belum dimanfaatkan, A mengetuk semua kartunya, memulai proses bunuh diri yang sama dengan cara membakar. Jika semua kartu non-Gunung A diketuk, dan gunung-gunung belum dimanfaatkan, B membiarkan semua kartu mereka belum dimanfaatkan. Ini akan menyebabkan A untuk melanjutkan bunuh diri mana sampai ia kehilangan permainan.

Ini harus memenuhi kriteria yang diminta dalam pertanyaan, dan karenanya ketika pemesanan ini diizinkan, saya percaya permainan ini Turing lengkap dalam arti yang dijelaskan dalam pertanyaan.

Alex Churchill, Stella Biderman dan Austin Herrick menerbitkan makalah ini yang menunjukkan bahwa Magic is Turing Complete

Abstract — Magic: The Gathering adalah permainan kartu perdagangan yang populer dan terkenal rumit tentang pertempuran sihir. Dalam makalah ini kami menunjukkan bahwa permainan optimal di Magic dunia nyata setidaknya sekeras Masalah Pemutusan, memecahkan masalah yang telah terbuka selama satu dekade [1], [10]. Untuk melakukan ini, kami menyajikan metodologi untuk menanamkan mesin Turing yang sewenang-wenang ke dalam permainan Magic sehingga pemain pertama dijamin akan memenangkan permainan jika dan hanya jika mesin Turing berhenti. Hasil kami berlaku untuk bagaimana Sihir yang sebenarnya dimainkan, dapat dicapai dengan menggunakan deck standar-hukum-turnamen, dan tidak bergantung pada stokastik atau informasi tersembunyi. Hasil kami juga sangat tidak biasa karena semua gerakan kedua pemain dipaksa dalam konstruksi. Ini menunjukkan bahwa bahkan mengenali siapa yang akan memenangkan pertandingan di mana tidak ada pemain yang memiliki keputusan non-sepele untuk membuat sisa permainan tidak dapat diputuskan. Kami menyimpulkan dengan diskusi tentang implikasi untuk teori komputasi game yang bersatu dan komentar tentang kemampuan bermain papan tersebut dalam pengaturan turnamen.