Mesin Turing alfabet tak terbatas

Apakah Mesin Turing yang diizinkan untuk membaca dan menulis simbol dari alfabet tak terbatas lebih kuat daripada TM biasa (itulah satu-satunya perbedaan, mesin masih memiliki sejumlah negara terbatas)?

Intuisi tidak memberi tahu saya, karena Anda memerlukan jumlah negara tak terbatas untuk membedakan setiap simbol. Jadi saya pikir beberapa simbol atau transisi yang disebabkan oleh simbol (atau beberapa himpunan bagian dari transisi) harus setara. Jadi, Anda dapat benar-benar mensimulasikan mesin tersebut dengan TM biasa dan subset terbatas dari simbol atau transisi tersebut.

Bagaimana saya bisa mendekati bukti formal ini?

Tidak, itu akan lebih kuat. Fungsi transisi tidak lagi terbatas, dan itu memberi Anda banyak daya.

Dengan alfabet tak terbatas, Anda dapat menyandikan item input apa pun dari himpunan tak terbatas dalam satu simbol (meskipun rangkaian input tidak boleh "lebih tak terbatas" dari himpunan alfabet, misalnya alfabet mungkin hanya akan tak terhingga, jadi unsur-unsur yang tak terhitung jumlahnya set seperti bilangan real tidak dapat direpresentasikan dalam satu simbol). Dan juga untuk output.

Jadi, Anda dapat membuat dua kondisi (satu inisial, satu menerima) tak terbatas-alfabet-TM dengan satu transisi yang bergerak ke kondisi terima dan mengubah simbol di bawah kepala pita sesuai dengan fungsi yang Anda coba hitung. Resep ini akan memungkinkan Anda untuk menghitung pemetaan antara set yang dapat dimasukkan dalam korespondensi satu-ke-satu dengan alfabet.

Jadi untuk menghindari jenis mesin yang merosot itu menjadi jawaban atas segalanya, Anda harus membatasi apa yang bisa dilakukan fungsi transisi. Yang jelas akan membutuhkan fungsi transisi itu sendiri yang dapat dihitung (fungsi transisi TM yang biasa memang sepele, karena mereka terbatas). Tetapi kemudian Anda akan mencoba menggunakan fungsi yang dapat dihitung untuk menentukan model fungsi yang dapat dihitung.

Jawaban di atas benar, tetapi ada sedikit lagi yang dapat dikatakan tentang huruf dan kemampuan komputer yang tak terbatas.

Mesin Turing dijelaskan dalam WP sebagai di mana semua set terbatas. Dengan demikian fungsi transisi harus terbatas.δ : Q / F × Γ → Q × Γ × { L , R $M = (Q, \Gamma,b,\Sigma,\delta, q_0, q_f)$

$$\delta: Q / F \times \Gamma \rightarrow Q \times\Gamma \times \{L,R \}$$

Dalam mesin alfabet tak terbatas kita akan mengganti alfabet input dengan say dan alfabet tape oleh dan fungsi transisi oleh mematuhi:Σ i n f Γ i n f δ i n $\Sigma$$\Sigma^{inf}$$\Gamma^{inf}$$\delta^{inf}$

$$\delta^{inf}: Q / F \times \Gamma^{inf} \rightarrow Q \times\Gamma^{inf} \times \{L,R \}$$

Jadi harus merupakan fungsi tanpa batas. Seperti dikatakan jika fungsi ini tidak dapat dikomputasi, maka di atas tidak dapat diwakilkan secara layak. Mari kita asumsikan bahwa kita akan menjaga (sebagian) rekursif jika memungkinkan. Pertanyaannya adalah apakah alfabet akan selalu memungkinkan ini.$\delta^{inf}$$\delta^{inf}$

Masalah dasarnya adalah bahwa alfabet terbatas disajikan secara keseluruhan (sehingga kita dapat memilih untuk mendefinisikan fungsi kita secara berulang), tetapi alfabet tak terbatas tidak pernah dapat disajikan secara keseluruhan. Jadi mekanisme apa yang menghasilkan alfabet?

Cara paling sederhana untuk mempertimbangkan ini adalah membayangkan bahwa ada alfabet "inti" yang terbatas, katakanlah . Kemudian hasilkan bahasa . Asumsikan bahwa string abaab . Kemudian tentukan . Jadi alfabet tak terbatas terdiri dari set string dari disatukan menjadi simbol tunggal seperti .$A=\{a,b\}$$L \subset A^*$ $\in L$$\alpha = <abaab> \in \Gamma^{inf}$$L$$<abaab>$

Alfabet yang paling sederhana pada dasarnya adalah <1 *> , bahasa reguler di mana dua simbol dibedakan dengan menghitung jumlah goresan vertikal di setiap simbol. Ini akan dapat dihitung dengan parser keadaan terbatas (sebagai LBA, bukan sebagai Finata Automata). Turing berpendapat alfabet terbatas untuk menghindari tampilan operasi yang tidak terbatas dalam operasi TM. Namun perlu dicatat bahwa 26 huruf alfabet Inggris tidak mengikuti pola penghitungan ini: huruf z tidak mengandung 26 garis atau titik atau apa pun. Jadi pola-pola lain dimungkinkan dengan pola komputasi paling umum yang didasarkan pada bahasa yang berulang secara berulang ( .$L$

Masalahnya di sini adalah bahwa membangun tidak akan mungkin kecuali definisi secara eksplisit disediakan. Ini sebagian karena kesetaraan set ulang tidak dapat diputuskan dan sebagian karena kalau tidak kita hanya punya sampel terbatas untuk bekerja dengan dan tidak dapat menyimpulkan dari itu. Jika kita memiliki definisi (dan karenanya ) maka jika rekursif dalam maka rekursif dalam hingga A, dan jadi benar-benar rekursif dan bisa bersifat rekursif.$\delta^{inf}$$L$$L$$L$$\Gamma^{inf}$$f$$\Gamma^{inf}$$f$$f$$\delta^{inf}$

Akhirnya kami mempertimbangkan kasus bahwa tidak kembali dengan dua contoh:$L$

Contoh1 . iff terbukti berbeda. Dalam hal ini alfabet jelas tidak akan memiliki deskripsi yang terbatas - melainkan akan "tumbuh" dari waktu ke waktu (dan hanya sepenuhnya didefinisikan sendiri dalam beberapa batas komputasi). Tapi kemudian itu adalah alfabet tak terbatas yang tidak dapat disajikan sekaligus dalam hal apa pun. Jadi, jika bersifat rekursif dalam , maka f ada di - . Jadi tidak bisa menjadi rekursif.$<n>\in \Gamma^{inf}$$\phi_{n}(n)$$\Gamma^{inf}$$f$$\Gamma^{inf}$$\Delta_2^0$$\delta^{inf}$

Contoh2 . Contoh yang lebih geometris mempertimbangkan Ubin seperti Penrose . Biarkan simbol jika adalah unit dari N ubin aperiodik yang terbukti dapat memasang ubin bidang. Alfabet ini tidak terbatas karena seseorang dapat membuat, untuk setiap N, unit N-ubin dari ubin Penrose. Namun ubin pesawat itu sendiri tidak dapat dipastikan, sehingga himpunan S akan tumbuh karena lebih banyak ubin seperti ini ditemukan. Kemungkinan rekursif dalam tetapi tidak sepenuhnya rekursif mungkin f (S) = jumlah ubin di S.$S\in\Gamma^{inf}$$S$$f$$\Gamma^{inf}$