Decidability dari labirin fraktal

Labirin fraktal adalah labirin yang berisi salinan dirinya sendiri. Misalnya, yang berikut oleh Mark JP Wolf dari artikel ini :

Mulailah di MINUS dan lanjutkan ke PLUS. Saat Anda memasukkan salinan labirin yang lebih kecil, pastikan untuk mencatat nama surat salinan itu, karena Anda harus meninggalkan salinan ini di jalan keluar. Anda harus keluar dari setiap salinan labirin bersarang yang telah Anda masukkan, meninggalkan dalam urutan terbalik yang Anda masukkan (misalnya: masukkan A, masukkan B, masukkan C, keluar C, keluar B, keluar A). Anggap saja sebagai serangkaian kotak bersarang. Jika tidak ada jalur keluar yang meninggalkan salinan bersarang, Anda telah menemui jalan buntu. Warna telah ditambahkan untuk membuat jalur lebih jelas, tetapi hanya dekoratif.

Jika ada solusi, pencarian pertama harus menemukan solusi. Namun, misalkan tidak ada solusi untuk labirin - maka program pencarian kami akan berjalan selamanya semakin dalam dan semakin dalam.

Pertanyaan saya adalah: diberi labirin fraktal, bagaimana kita dapat menentukan apakah ia memiliki solusi atau tidak?

Atau sebagai alternatif, untuk labirin fraktal dari ukuran yang diberikan (jumlah input / output per salinan), apakah ada batas panjang solusi terpendek? (Jika ada ikatan seperti itu, kita hanya bisa mencari sedalam itu secara eksotis)

Algoritme informal cepat untuk membuktikan bahwa masalahnya dapat ditentukan:

• misalkan ada Input / Output I 1 , . . . Saya n ;$n$$I_1,...I_n$
• buat grafik mana setiap I i , M I N U S dan P L U S adalah node, dan ganti setiap labirin bersarang M j dengan subgraph K n (grafik lengkap); tambahkan tepi antara I i , M I N U S , P L U S , M j I k sesuai dengan labirin; pertahankan "extern" M j I I → M $G$$I_i$$MINUS$$PLUS$$Mj$$K_n$$I_i, MINUS, PLUS, Mj_{I_k}$ edge berbeda dari edge "internal" yang bersesuaianIi→IkdariMjsebagai subgraf lengkap;$Mj_{I_i} \rightarrow Mj_{I_k}$$I_i \rightarrow I_k$$Mj$
• sebutkan semua jalur dari MINUS ke PLUS dalam (menghindari siklus);$G$
• Jika Anda menemukan jalur yang tidak melintasi salinan bersarang, maka itu adalah solusi; jika tidak perluas setiap jalur "internal" dari labirin bersarang dari setiap jalur:$Mj$

Misalkan lintasan dalam enumerasi pertama adalah , maka path adalah solusi yang valid jika ada jalur dari I i → I j dan dari I k → I h di labirin asli (grafik G ).$MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$$I_i \rightarrow I_j$$I_k \rightarrow I_h$$G$

Jadi kita harus memperluas dengan dan B aku k → B I h traversals pencacahan semua jalan dari saya saya untuk saya k dan dari saya k ke saya h di G .$A_{I_i} \rightarrow A_{I_j}$$B_{I_k} \rightarrow B_{I_h}$$I_i$$I_k$$I_k$$I_h$$G$

Loop tak terbatas terdeteksi ketika kita pencacahan semua jalur dari ke saya k dalam perluasan jalan yang dalam tahap sebelumnya sudah terkandung . . . → M I i → M I k → . . . untuk beberapa submaze M (hanya ada n 2 ekspansi yang mungkin).$I_i$$I_k$$... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$$M$$n^2$

Sebuah solusi ditemukan jika kita menemukan perluasan jalur yang hanya berisi input / output ; labirin tidak punya solusi jika kita tidak bisa memperluas jalur tanpa loop.$I_i$

Ini bukan "jawaban" untuk pertanyaan saya, melainkan komentar panjang yang mungkin menarik orang di sini.

Saya mengklaim bahwa ada definisi "tipe analisis" alami dari sebuah labirin dan solusi, dan itu berbeda dari definisi ilmu-komputer / grafik-teori yang kami gunakan di sini. Secara khusus, Anda dapat memiliki labirin fraktal yang memiliki "solusi" di bawah definisi analisis, tetapi akan dinyatakan tidak dapat diselesaikan oleh algoritma Marizio De Biasi dan teknik pushdown automata Peter Shor.

Definisi: Sebuah labirin adalah bagian kompak dari pesawat M ⊂ R 2 yang berisi titik awal dan titik akhir s , e ∈ M , masing-masing. Sebuah solusi adalah fungsi kontinu f : [ 0 , T ] → M sehingga f ( 0 ) = s dan f ( T ) = e .$M$$M \subset \mathbb{R}^2$$s,e \in M$$f:[0,T] \rightarrow M$$f(0)=s$$f(T)=e$

Sekarang perhatikan Kurva Hilbert :

Seseorang dapat menafsirkan kurva ini sebagai "labirin fraktal" dengan diagram berikut:

$P$

$P = APA^{-1}BPB^{-1}CPC^{-1}DPD^{-1}$

Sekarang Anda mungkin berpendapat bahwa ini tidak dalam semangat labirin fraktal karena kurva Hilbert mengisi seluruh kotak dan karena itu Anda bisa menggambar segmen garis lurus dari awal hingga akhir. Keberatan ini mudah ditimpa - cukup gunakan diagram kurva hilbert yang disematkan secara langsung, seperti yang ditunjukkan di sini:

Ini juga mengandung urutan lintasan kontinu yang seragam konvergen mulai dari awal hingga akhir, dengan argumen yang sama yang digunakan untuk menunjukkan konvergensi seragam kurva Hilbert. Namun itu adalah "labirin fraktal" sejati dalam arti bahwa itu tidak mengisi seluruh ruang.

Jadi kita memiliki labirin fraktal yang dipecahkan oleh definisi analitik, tetapi tidak dapat dipecahkan oleh grafik definisi teoretis ..!?

Ngomong-ngomong, saya cukup yakin bahwa logika saya benar, tetapi tampaknya berlawanan dengan intuisi sehingga jika ada yang bisa menjelaskan hal ini, saya akan sangat menghargainya.