Sub bahasa tidak dikenali Turing, atau mungkinkah itu?

10

Biarkan A dan B menjadi bahasa dengan A ⊆ B, dan B dikenali Turing. Bisakah A menjadi Turing-dikenali? Jika ya, apakah ada contoh?

computability Gfe
sumber

18

Ini adalah sesuatu yang membingungkan banyak siswa. Intinya di sini adalah bahwa menjadi bagian dari bahasa lain tidak menyiratkan banyak tentang kesulitan komputasi mereka. Anda selalu dapat mempertimbangkan trivial bahasa dan dan bahasa lain di antaranya menggunakan pengaturan inklusi. $\emptyset$ $\Sigma^*$

Oleh karena itu hanya mengetahui bahwa suatu bahasa mengandung atau terkandung dalam bahasa yang mudah dihitung tidak mengatakan apa-apa tentang kesulitan menghitungnya.

Kaveh
sumber

Tetapi saya tidak dapat menemukan bahasa subset dari Σ ∗ yang tidak dapat dikenali Turing.

Gfe

3

@ Willhelm, ambil bahasa apa pun yang tidak dapat dikenali Turing dan akan berfungsi.

Kaveh

Begitu, jadi saya bisa menggunakan masalah penghentian untuk membuktikan bahwa ada bahasa seperti itu.

gfe

@ Willhelm, ya. :)

Kaveh

1

Ketika bahasa Turing-dikenali adalah tidak decidable, itu berarti bahwa tidak co-Turing-dikenali (dengan kata lain: tidak dikenali). Karena adalah himpunan bagian yang benar-benar valid dari , ini mendukung fakta bahwa untuk bahasa mana dapat dikenali-Turing, mungkin sangat tidak baik. $X$ $X^c$ $X^c$ $\Sigma^*$ $A \subseteq B$ $B$ $A$

Sander
sumber

Saya pikir jawaban Kaveh lebih baik dan lebih tepatnya. Bahasa apa pun adalah himpunan bagian dari dan kami tahu bahwa dapat dipilih dan bahwa ada bahasa keras yang sewenang-wenang.

Σ^{*}

$\Sigma^*$

Σ^{*}

$\Sigma^*$

Pål GD

Itulah yang saya coba jelaskan, karena

bisa bahasa apa pun, karena

otomatis berlaku. ;)

X

$X$

X \subset Σ^{*}

$X \subset \Sigma^*$

Sander

-3

Diskusi Anda berhasil membingungkan saya :(

"Bisakah A tidak bisa dikenali Turing?"

Saya merasa A selalu dikenali Turing . Inilah pemikiran saya,

Karena B adalah Turing Diakui => Ada beberapa TM yang menerima semua kata-kata bahasa B => Ada TM yang menerima (semua kata-kata bahasa A + beberapa kata lain) => Ada TM yang menerima semua kata-kata bahasa A => A adalah Turing Diakui.

Apakah ini salah? Dapatkah ada kasus di mana A adalah Non-TRL sedangkan B adalah TRL. Mohon bantuannya

bongubj
sumber

1

Ya, itu salah: akseptor untuk suatu bahasa tidak boleh menerima kata apa pun kecuali yang ada dalam bahasa tersebut.

reinierpost

Tolong jangan posting pertanyaan tindak lanjut sebagai jawaban. Gunakan komentar (setelah Anda membuktikan pada sistem bahwa Anda dapat dipercaya) atau buat posting baru jika pertanyaan baru sangat berbeda (tidak demikian halnya di sini).

Raphael

-4

Dalam hal ini A tidak bisa dikenali Turing. Ambil ini sebagai contoh:

Bahasa B adalah gabungan dari tr bahasa (C) dan bahasa bukan tr (A). Anda dapat membuat mesin turing yang mengenali B. A tidak tr dan A ⊆ B.

Apakah itu benar? saya tidak tahu apakah itu..so .. =)

Philip A.
sumber

3

C \in R E

$C\in RE$

A \notin R E

$A\notin RE$

C = \emptyset

$C=\emptyset$

A

$A$

B = A \cup C

$B=A \cup C$

Sub bahasa tidak dikenali Turing, atau mungkinkah itu?

Jawaban: