Apakah ada bahasa yang dapat diperhitungkan Turing yang tak terhitung?

17

Ada banyak (dan maksud saya banyak) bahasa yang dapat dihitung yang dapat didekati oleh Turing. Bisakah bahasa yang tak terhitung dapat menjadi pilihan Turing?

Jyotirmoy Pramanik
sumber
1
Jika bahasa dari semua kata yang mungkin adalah tak terhitung (yang membutuhkan alfabet tak terhitung) maka segera memberikan contoh dari (tafsiran) Turing bahasa terhitung tak terhitung. Jika tidak (yaitu, itu dapat dihitung), maka subbahasa juga tidak terhitung.
Marc van Leeuwen

Jawaban:

24

Setiap bahasa dengan alfabet terbatas (atau bahkan dapat dihitung) dapat dihitung. Dengan asumsi alfabet mesin Turing Anda terbatas, bahasa apa pun yang dapat diterima dapat dihitung.

Yuval Filmus
sumber
Bagaimana dengan set semua bahasa dengan jumlah terbatas string di atas alfabet yang tak terhitung jumlahnya? Apakah ini dapat dihitung atau tidak terhitung? Juga saya tidak bisa memikirkan bukti untuk "bahasa lebih dari alfabet tak terhingga jumlahnya dapat dihitung".
anir
Perangkat Anda juga dapat dihitung.
Yuval Filmus
Ini membuktikan "set bahasa lebih dari alfabet hingga dapat dihitung". Saya merasa kita dapat membuktikan "set bahasa yang berisi string tak terhingga tak terbatas atas alfabet terbatas dapat dihitung" mengikuti pendekatan bukti yang sama karena alfabet terbatas. Tetapi saya tidak dapat membayangkan bagaimana pendekatan ini dapat diadaptasi untuk alfabet yang tak terhitung jumlahnya.
anir
Anda tidak dapat membuktikannya karena itu salah. Jumlah urutan biner tak terbatas sudah tak terhitung.
Yuval Filmus
11

Kita dapat memiliki bahasa yang tak terhitung hanya jika kita mengizinkan kata-kata dengan panjang tak terbatas, lihat misalnya bahasa biasa Omega . Bahasa-bahasa ini disebut -bahasa. Contoh lain adalah bahasa subset real yang berisi, katakanlah, ekspansi desimal dari semua bilangan real.ω

Ada beberapa model di mana Mesin Turing dimodifikasi untuk menerima -bahasa. Beberapa model ini menggunakan kondisi Buchi untuk penerimaan. Karena Anda tidak dapat melihat seluruh input dalam waktu yang terbatas, kami katakan bahwa input diterima jika Mesin Turing memasuki kondisi terima berkali-kali. Jika kita dapat membuktikan ini dengan menganalisis input (bukan dengan menjalankannya), kita mengatakan bahwa input diterima.ω

Shreesh
sumber
1
Mengapa alfabet perlu dihitung?
leftaroundtentang
2
Setiap model yang dipelajari memiliki alfabet hingga. Jika alfabet juga menjadi tak terbatas (dapat dihitung atau tidak terhitung) sulit untuk memiliki model yang masuk akal.
Shreesh
@Shreesh Nah, jika alfabetnya tak terhitung, pemetaan naif dari FSM (dengan transisi tak terhitung antara sejumlah negara terbatas) mungkin agak kuat?
Yakk
1
Benar, ini adalah jenis ekstensi, yang mungkin memiliki kelas bahasa yang mungkin merupakan superkelas RE atau bahasa rekursif. Tetapi mereka tidak dipelajari dengan baik, jika dipelajari sama sekali. Masalah terbesar adalah, menurut saya, bagaimana kita bisa memberikan representasi mesin yang terbatas. Maka Anda harus menulis simbol dalam sel rekaman. Bahkan sel yang rendah hati mungkin membutuhkan memori tak terbatas untuk menyimpan deskripsi simbol kaset yang sedang ditulis.
Shreesh
Ini penjelasan yang bagus. Saya akan menambahkan bahwa meskipun kriteria penerimaan / penolakan yang biasa digunakan, Anda dapat mengatakan bahwa masih ada beberapa bahasa yang dapat diputuskan oleh mesin Turing dan secara teknis memiliki banyak string, tetapi hanya karena sebagian besar karakter adalah " tidak berguna "ke bahasa.
Owen
4

Komputasi klasik membahas fungsi lebih dari string hingga dari alfabet terbatas. Akibatnya, semua bahasa, baik yang dapat ditentukan atau tidak, dapat dihitung.

Untuk mempertimbangkan bahasa yang tak terhitung, kita harus melihat string tak hingga menggantikan string terbatas. (AFAIK, memiliki alfabet tak terbatas tidak terlalu menarik dan tidak sesuai dengan model perhitungan yang realistis dengan sendirinya.)

Ada beberapa model perhitungan di mana kita dapat berurusan dengan string tak terbatas yang memungkinkan kita untuk mewakili objek dari domain yang tak terhitung seperti angka nyata. Ini sering direpresentasikan sebagai perhitungan tipe yang lebih tinggi. Salah satu model yang menggunakan mesin Turing adalah model TTE. Dalam model ini input dapat berupa string tak terbatas dan mesin dapat mengakses item apa pun dalam string yang diinginkan. Mesin tidak perlu berhenti, namun ada beberapa kondisi untuk memastikan output mesin menyatu.

Mari kita asumsikan bahwa input mesin kita berasal dari , yaitu string tak terbatas dari alfabet Σ , misal Σ = { 0 , 1 } . Lalu ada Σ N = 2 N string. Oleh karena itu ada 2 2 N bahasa yang memungkinkan. Jumlah mesin TTE Turing masih dapat dihitung. Jadi sebagian besar bahasa ini tidak dapat dipastikan.ΣωΣΣ={0,1}ΣN=2N22N

Tetapi ada sesuatu yang lebih menarik di sini: jika Anda ingin mesin berhenti selalu hanya akan dapat membaca bagian awal input yang terbatas. Akibatnya kami memiliki yang berikut: Biarkan menjadi mesin TTE yang selalu berhenti (dalam waktu yang terbatas). Kemudian ada awalan bebas bahasa L Σ * dan mesin Turing N sehingga untuk setiap x Σ ohm , M menerima x IFF N menerima bagian awal dari x yang di L .MLΣNxΣωMxNxL

Singkatnya , perhitungan mesin TTE Turing yang selalu berhenti ditentukan oleh perhitungan mesin Turing pada string terbatas.


Izinkan saya memberikan beberapa contoh bahasa string tak terbatas yang dapat ditentukan dan tidak dapat diputuskan:

  1. Untuk setiap bahasa string tak terbatas yang posisi k th adalah 0 dapat ditentukan. Sama dengan posisi k menjadi 1. Persimpangan dari dua bahasa yang dapat dipilih dapat ditentukan, misalnya string yang posisi ke- 3 adalah 0 dan posisi ke- 6 adalah 1.kNkk36

  2. Gabungan dari dua bahasa yang dapat diputuskan mana pun dapat dipilih. Misalnya string yang dimulai dengan atau 10 .010

  3. Biarkan menjadi daftar terhitung bahasa yang dapat dihitung. Kemudian L = i L i adalah semi-decidable, yaitu ada mesin yang perhentian dan menerima setiap kali string dalam L dan tidak menerima ketika string tidak dalam L . Jika tidak ada di L mesin mungkin tidak berhenti. Setiap bahasa semi-decidable dapat diperoleh melalui penyatuan daftar bahasa yang dapat dihitung dari formulir yang diberikan dalam item 1 di atas.LiL=iLiLLL

  4. Suatu bahasa dapat ditentukan jika bahasa dan pelengkapnya semi-decidable.

  5. kk


xlgxxlgx untuk kita.


f{0,1}f1(1)". Ada juga banyak referensi lain di situs web untuk Komputasi dan Kompleksitas dalam Analisis Jaringan .

Kaveh
sumber
1
" Akibatnya, semua bahasa terbatas " - Apakah maksud Anda dapat dihitung?
Anton Trunov
Saya kira begitu, Tuan Trunov.
Jyotirmoy Pramanik
Ini adalah posting yang bagus tapi saya gagal melihat apa hubungannya dengan pertanyaan spesifik yang diajukan di sini. Mungkin Anda ingin membuat pasangan tanya-jawab?
Raphael