Apakah ada automata yang tidak terbatas?

Dalam teori automata, kita semua membaca automata sebagai automata terbatas, sejak awal. Yang ingin saya ketahui adalah, mengapa automata terbatas? Untuk lebih jelasnya, apa yang ada dalam otomat yang terbatas - alfabet, bahasa, string yang dibuat dengan ekspresi reguler, atau apa? Dan apakah ada (secara teori) automata non-terbatas?

Semua model robot yang biasanya Anda temui akan terwakili secara halus; jika tidak akan ada banyak yang tak terhitung jumlahnya, yang berarti mereka tidak ditangkap oleh model lengkap Turing. Atau, dalam CS-think, mereka tidak akan berguna¹.

"Finite automata" disebut terbatas karena mereka hanya memiliki satu set konfigurasi yang terbatas (input string disamping). Automata pushdown, misalnya, memiliki tumpukan yang dapat memiliki konten sewenang-wenang - ada banyak kemungkinan konfigurasi.

Nota bene: Konfigurasi PDA masih terwakili secara terbatas! Faktanya, setiap model komputasi yang termasuk dalam Turing-computability harus memiliki konfigurasi yang terwakili secara halus, jika tidak TMs tidak akan dapat mensimulasikannya.

1. Saya secara sadar mengabaikan hiperkomputasi di sini untuk tujuan pertanyaan ini.

Nama lengkapnya adalah "finite state automata". Bagian yang krusial adalah bahwa keadaan otomat dapat sepenuhnya dikarakterisasi oleh suatu elemen dari sejumlah keadaan diskrit yang terbatas. Ini berarti bahwa jika keadaan (yang relevan) dari otomat melibatkan variabel bernilai nyata, terdapat jumlah potensial tak terhingga (mengesampingkan keterbatasan representasi titik apung), dan otomat tidak terbatas.

Ini mungkin tidak pernah terjadi dalam ilmu komputer teoretis, tetapi itu tidak terlalu eksotis dalam domain pemodelan urutan bilangan real. Hidden Markov Models dapat digunakan untuk memodelkan urutan angka sebagai output dari sistem probabilistik yang terdiri dari satu filter output untuk setiap keadaan model Markov (diskrit, terbatas) dengan keadaan yang tidak dapat diobservasi. Filter menghitung output bernilai riil berikutnya dari vektor output sebelumnya (model "autoregresif"), tetapi model Markov yang mendasarinya terbatas karena probabilitas transisinya hanya bergantung pada keadaan Markov saat ini.

Namun, artikel ini ( teks lengkap ) mengembangkan variasi di mana probabilitas transisi juga bergantung pada vektor bilangan real dari output sebelumnya. Keadaan sistem ini adalah kombinasi dari keadaan Markov diskrit dan tupel bilangan real ("model Markov keadaan campuran"), sehingga dapat dalam jumlah tak terbatas dari berbagai negara.

Singkatnya, automata tidak terbatas secara teori didefinisikan dengan baik, dan kadang-kadang bahkan ditemui.

Dalam otomat terbatas, ada sedikit keterbatasan: jumlah negara, ukuran alfabet yang mendasarinya, dan panjang string yang diterima oleh mesin.

Anda tentu dapat mengendurkan kondisi keterbatasan ini dengan memungkinkan, katakanlah, mesin memiliki banyak keadaan tanpa batas, tetapi jika Anda melakukannya, mesin yang dihasilkan menjadi tidak menarik, dalam arti bahwa mesin tersebut dapat dirancang untuk menerima bahasa apa pun.

Faktanya, dalam teori automata (yang jauh berbeda dari asal-usul Kleene, Rabin dan Scott), ada banyak bentuk automata yang tidak terbatas. Ini muncul karena beberapa alasan.

Automata pushdown , misalnya, adalah automata yang memiliki serangkaian konfigurasi tak terbatas (ini memiliki sejumlah negara terbatas, tetapi kenyataannya adalah ini harus dianggap sebagai 'automata tak terbatas').

Dalam nada yang sama, ada contoh-contoh lain dari automata tak terbatas di mana ruang keadaan tidak terbatas, tetapi dengan banyak struktur. Misalnya seseorang menganggap kelas automata yang memiliki ruang keadaan sebagai (dimensi terbatas) ruang vektor, dan sebagai fungsi transisi peta linear (ditambah beberapa inisial dan hal-hal akhir). Ini dikenal sebagai automata tertimbang di atas bidang dasar (karena Schützenberger di 61). Ini dapat diminimalkan dan diuji untuk kesetaraan. Contoh lain termasuk register automata ( automata ini memiliki set register yang terbatas, dan mengerjakan alfabet tak terbatas: ini dapat membandingkan huruf dengan register dan menyimpan huruf dalam register), dan bentuk automata nominal yang lebih modern(yang memiliki ekspresi yang sama, tetapi memiliki fondasi dan properti yang lebih baik). Kekosongan automata seperti itu dapat ditentukan.

$A^*$$a$$u$$ua$, dan sebuah negara menerima jika itu milik L). Ada juga objek terakhir (yang memiliki bahasa sebagai negara!). Keberadaan dua objek ini adalah salah satu cara untuk menjelaskan pada tingkat tinggi mengapa automata deterministik dapat diminimalkan dan terkait erat dengan kongruensi Myhill-Nerode.

Untuk menyimpulkan, ada automata tak terbatas, tetapi model yang pertama kali dipelajari dalam kuliah selalu yang terbatas.

Saya pikir pertanyaannya adalah mengasumsikan kesimpulan bahwa tidak ada automata keadaan tak terbatas ketika ada, mereka hanya tidak layak untuk diangkat.

Dalam Teori Automata, ada hierarki kekuatan model virtual yang berbeda. Yang saya pelajari memiliki 4 (yang saya ingat, sudah beberapa waktu), yang saya temukan di Wikipedia memiliki 5. Yang terlemah di kedua automata keadaan terbatas, dan yang terkuat adalah mesin Turing. Ada beberapa konsep level yang lebih kuat daripada mesin Turing yang secara longgar disebut komputasi hyper. Banyak deskripsi berbeda dari mesin virtual termasuk dalam salah satu level ini. Mesin Turing secara khusus dikenal untuk banyak model yang semuanya memiliki tingkat daya komputasi yang sama.

Automata keadaan tak terbatas, setidaknya satu yang didefinisikan secara formal, akan jatuh ke dalam salah satu level ini. Mungkin ada sesuatu yang sedikit menarik dalam menunjukkan bagaimana definisi ketat dari automata keadaan tak terbatas cocok ke dalam salah satu level ini, tetapi selain itu, tidak akan banyak berguna mengingat ada mesin virtual yang jauh lebih baik dipelajari yang mewakili setiap level . Ini mirip dengan bagaimana tidak ada banyak minat dalam satu miliar pita mesin Turing, karena itu tidak akan lebih kuat dari satu mesin pita Turing tetapi lebih rumit untuk dihadapi.

Sekarang, jika Anda kebetulan menemukan automata status tak terbatas yang tidak setara dengan tingkat hierarki yang ada, itu mungkin menarik. Tapi tanpa itu, automata keadaan tak terbatas sudah ditangkap dalam hierarki yang ada, dan mengingat komplikasi tambahan yang berhubungan dengan infinity, kita hanya menghindarinya dengan cara yang sama kita menghindari model mesin Turing yang terlalu rumit.

Versi tak terbatas (naif) mesin keadaan terbatas deterministik terlalu kuat . Hal seperti itu akan mampu "menghafal" bahasa apa pun, jadi tidak banyak yang bisa dipelajari dari mempertimbangkannya.

Misalnya, di atas alfabet biner, pertimbangkan otomat dalam bentuk pohon biner lengkap dengan ketinggian tak terbatas. Setiap string yang mungkin Anda pertimbangkan sebagai input sesuai secara unik dengan simpul pohon, sehingga Anda dapat membuat penentu untuk bahasa apa pun hanya dengan membuat node yang sesuai menerima status.