Apakah ada properti automata yang tidak dapat dipastikan tidak lengkap?

15

Apakah ada properti yang tidak dapat ditentukan dari automata terbatas linier (menghindari trik bahasa set kosong)? Bagaimana dengan robot terbatas deterministik? (kesampingkan keras kepala).

Saya ingin mendapatkan contoh (jika mungkin) dari masalah yang tidak dapat ditentukan yang didefinisikan tanpa menggunakan mesin Turing secara eksplisit.

Apakah Turing kelengkapan model diperlukan untuk mendukung masalah yang tidak dapat diperhitungkan?

computability automata undecidability Hernan_eche
sumber

"Apakah ada solusi untuk sistem persamaan Diophantine ini?" Apakah ini yang Anda tanyakan? Bagi saya tidak jelas apa yang Anda inginkan. Tapi, masalah yang saya berikan tidak dapat dipastikan dan tidak menyebutkan TM, jadi, sebenarnya, tampaknya memenuhi persyaratan paragraf kedua Anda.

rgrig

Memutuskan apakah dua pushdown automata mengenali kata yang sama tidak dapat diputuskan serta masalah lain tentang pushdown automata . Saya tidak bisa memikirkan masalah yang tidak dapat dipastikan yang melibatkan DFA.

jmad

1

Jawaban atas pertanyaan "Apakah mungkin membuat masalah yang tidak dapat diputuskan untuk robot yang kurang kuat daripada Mesin Turing" adalah ya . Bahkan, untuk setiap jenis otomat, seseorang selalu dapat mengidentifikasi masalah yang tidak dapat diputuskan.

Amelio Vazquez-Reina

1

Mengingat jawaban yang diterima, saya mengulangi pertanyaan untuk menanyakan apa yang diinginkan OP (tampaknya).

Raphael

15

Masalah yang tidak dapat dipikirkan tentang tata bahasa bebas konteks, dan karenanya, akseptor pushdown juga, yang dibatasi TMs dari Wikipedia ...

Diberikan CFG, apakah ia menghasilkan bahasa semua string di atas alfabet simbol terminal yang digunakan dalam aturannya?
Dengan dua CFG, apakah mereka menghasilkan bahasa yang sama?
Dengan dua CFG, dapatkah yang pertama menghasilkan semua string yang bisa dihasilkan yang kedua?

Ada banyak lainnya tentang CFG / PDA serta CSGs / LBA dan banyak model "lebih sederhana daripada TM" lainnya.

David Lewis
sumber

+1, terima kasih, saya masih tergoda untuk bertanya tentang yang lebih sederhana daripada CFG, dan seterusnya .. untuk mencari tahu mana yang merupakan masalah automata + pertama (lebih sederhana) yang tidak dapat diputuskan

Hernan_eche

3

Untuk menemukan masalah "sederhana" atau "paling sederhana" yang tidak dapat diputuskan, atau memiliki properti apa pun, Anda memerlukan definisi tepat "sederhana", yang banyak di antaranya mungkin. Tetapi yang klasik dalam automata dan bahasa formal adalah "level dalam hierarki Chomsky" (yang sebenarnya tidak terlalu hirarki, secara matematis - pada awalnya diusulkan untuk tata bahasa bahasa alami). FSA adalah yang terendah, dan saya cukup yakin masalah yang tidak dapat dipastikan untuk FSA harus merujuk dalam beberapa cara "esensial" untuk formalisme "kurang sederhana" (semua membutuhkan definisi yang tepat). CFL / CFG adalah tertinggi berikutnya, jadi saya memilih itu.

David Lewis

+1 Saya setuju, menemukan minimum juga tidak dapat diputuskan, yang mengejutkan adalah tidak mungkin untuk membangun masalah yang belum diputuskan untuk FSA, maka mungkin untuk CFG, hanya tergoda untuk menemukan sesuatu di antaranya, terima kasih

Hernan_eche

1

@Hernan_e - terdapat struktur model dan bahasa sub-CFL yang sangat kaya - misalnya, pda / family 1-counter, yang menggunakan "counter" bilangan bulat positif alih-alih pda; pda n-turn, yang hanya memungkinkan lilitan dari peningkatan ke penurunan tumpukan, dan generalisasi dari itu. Dan ada banyak masalah yang tidak dapat dipastikan tentang hal itu, serta pertanyaan terbuka tentang struktur, misalnya: apakah ada CFL "minimal" non-reguler dalam beberapa gagasan yang tepat tentang "minimal". Tetapi hal ini biasanya di tingkat sarjana dan / atau penelitian.

David Lewis

7

Tidak jelas apa yang Anda tanyakan di bagian akhir pertanyaan terutama karena "masalah tentang model mesin" tidak didefinisikan.

Saya ingin mendapatkan contoh (jika mungkin) masalah yang tidak dapat diputuskan tanpa membutuhkan Mesin Turing

Biarkan menjadi menjadi kelas mesin dan mari gunakan sebagai kode . Kita bisa menafsirkan juga sebagai kode TM th dan kemudian meminta diberikan melakukan th TM berhenti? Dan masalah ini tentang s adalah diputuskan. $\{M_i\}$ $i$ $M_i$ $i$ $i$ $M_i$ $i$ $M_i$

Bahasa hanyalah seperangkat string, interpretasi apa yang Anda tetapkan untuk string tidak berpengaruh pada kepantasan bahasa. Kecuali jika Anda secara resmi mendefinisikan apa yang Anda maksudkan dengan model mesin dan masalah tentang mesin-mesin itu, pertanyaan Anda nanti tidak dapat dijawab.

Apakah Turing menyelesaikan mesin minimal untuk mendukung masalah yang tidak dapat diputuskan?

Sekali lagi, poin yang saya sebutkan di atas berlaku. Pertanyaan yang lebih masuk akal adalah: apakah semua bukti keraguan dapat diputuskan melalui sesuatu yang mirip dengan keraguan tentang masalah penghentian untuk TM? (Jawabannya adalah: ada cara lain).

Pertanyaan lain yang mungkin adalah: apa subset terkecil dari TM di mana masalah penghentian bagi mereka tidak dapat diputuskan. Jelas kelas semacam itu harus mengandung masalah yang tidak berhenti (jika tidak, masalahnya bisa dianggap remeh). Kita dapat dengan mudah membuat himpunan bagian buatan TM di mana masalah penghentian tidak dapat diputuskan tanpa mampu menghitung apa pun yang bermanfaat. Pertanyaan yang lebih menarik adalah tentang set besar TM yang dapat di decidable di mana penghentian itu diperuntukkan bagi mereka.

Inilah poin lain: segera setelah Anda memiliki kemampuan yang sangat kecil untuk memanipulasi bit (misalnya ukuran polinomial ) Anda dapat membuat mesin dengan tiga input: , , dan sedemikian sehingga menghasilkan 1 jika f adalah menghentikan penerimaan perhitungan TM pada input . Maka Anda dapat menanyakan masalah seperti: apakah ada st adalah 1? yang merupakan masalah yang tidak dapat ditentukan. $\mathsf{CNF}$ $N$ $e$ $x$ $c$ $c$ $M_e$ $x$ $c$ $N(e,x,c)$

Kaveh
sumber

5

Ada masalah yang tidak dapat dipastikan sangat sederhana untuk automata keadaan terbatas. Pisahkan alfabet menjadi dua bagian , di mana huruf-huruf dalam adalah salinan "dilarang". Sekarang, mengingat keadaan terbatas otomat lebih $\Sigma \cup \bar\Sigma$ $\bar\Sigma$ $A$ $\Sigma\cup\bar\Sigma$ memutuskan apakah ia menerima string sedemikian rupa sehingga bagian yang tidak diblokir sama dengan bagian yang dilarang (jika kita mengabaikan bilah). Misalnya, tali akan ok (kedua bagian mantra ). $a a \bar a \bar a b\bar b \bar aa$ $aaba$

Ya, ini adalah Masalah Pasca Korespondensi yang disembunyikan dalam otomat keadaan terbatas. Kelengkapan Turing jauh dari jelas dalam pertanyaan. Itu ada di sana, di latar belakang, ketika dua salinan (tidak diblokir dan dilarang) bersama-sama kode antrian, yang itu sendiri adalah kekuatan Turing.

Hendrik Jan
sumber

Anda punya referensi tentang ini? tidak jelas bagaimana mengkonversi PCP ke ini. fyi ada juga beberapa masalah yang tidak dapat dipastikan dengan "transduser" FSM.

vzn

1

(1) Anda benar, itu sebenarnya terkait dengan masalah dua-pita , bilah yang menunjukkan pita kedua. (2) Hubungan dengan PCP sebagai berikut. Contoh PCP terdiri dari dua daftar kata

,

. Sekarang bahasa reguler yang mengkode PCP adalah

(u_{1}, \dots, u_{n})

$(u_1,\dots,u_n)$

(v_{1}, \dots, v_{n})

$(v_1,\dots,v_n)$

, di mana

adalah salinan yang dilarang dari

{u_{1} {\bar{v}}_{1}, \dots, u_{n} {\bar{v}}_{n}}^{+}

$\{ u_1\bar v_1, \dots, u_n\bar v_n \}^+$

\bar{v}

$\bar v$

. Saya khawatir saya tidak punya referensi.

v

$v$

Hendrik

3

"Apakah mungkin untuk membuat masalah yang tidak dapat ditentukan untuk otomat yang kurang kuat daripada Mesin Turing?"

Iya. Otomat adalah perumusan aksiomatik yang konsisten dari teori bilangan (misalnya lihat (1) ) dan oleh karena itu oleh teorema ketidaklengkapan pertama Gödel, ia harus memasukkan proposisi yang tidak dapat ditentukan.

Contoh:

Masalah apa pun yang tidak dapat diputuskan untuk TM juga tidak dapat diputuskan untuk robot apa pun yang dapat disimulasikan oleh TM. Mengapa? Karena jika otomat yang kurang kuat daripada TM dapat memutuskan bahasa yang tidak dapat diputuskan oleh TM, TM harus dapat memutuskannya dengan mensimulasikan automaton tersebut dengan menghasilkan kontradiksi.

Amelio Vazquez-Reina
sumber

2

Pertanyaan apakah LBA berhenti atau tidak juga dapat dipilih untuk TM, jadi itu bukan bagian dari contoh yang saya berikan dalam jawaban saya. Masalah apa pun yang tidak dapat diputuskan untuk TM juga tidak dapat diputuskan untuk LBA.

Amelio Vazquez-Reina

1

{T | T M T h a l t s o n i n p u t T}

$\{T|TM T halts on input T\}$ yang jelas bukan decidable, tapi itu dibuat-buat. Itu mungkin bisa diformalkan.

David Lewis

1

{T | TM T (T) halts}

$\{T|\text{ TM } T(T) \text{ halts}\}$

1

@DavidLewis roseck tidak mengklaim bahwa masalah yang tidak dapat diputuskan tentang TM masih belum dapat dipastikan jika Anda menafsirkannya sebagai tentang BBL. roseck hanya menyatakan bahwa jika ada masalah yang tidak dapat diputuskan oleh TM maka masalah yang sama persis tanpa reinterpretasi juga tidak dapat diputuskan oleh apa pun yang dapat disimulasikan oleh TM. Masalah penghentian TM dan masalah penghentian LBA adalah dua masalah yang berbeda.

Ben

1

@ Ben - jika demikian, maka "... tidak dapat diputuskan untuk otomat apa pun yang ..." harus " oleh ". Tapi itu pernyataan sepele.

David Lewis

1

Emil Post ingin menemukan jawaban untuk pertanyaan ini: Apakah ada set non-rekursif (non-computable) yang tidak menyelesaikan masalah penghentian. Dia hanya berhasil sebagian, tetapi apa yang dia lakukan, adalah menciptakan apa yang disebut set sederhana .

Dari Wikipedia:

Subset dari naturals disebut sederhana jika itu co-infinite dan recumerable enumerable, tetapi setiap subset infinite komplemennya gagal untuk disebutkan secara rekursif. Set sederhana adalah contoh set enumerable rekursif, yang tidak rekursif. Lihat artikel Wikipedia untuk informasi lebih lanjut dan referensi, set sederhana .

Pål GD
sumber

Apakah ada properti automata yang tidak dapat dipastikan tidak lengkap?

Jawaban: