Apakah ada bahasa terbatas dari kata-kata terbatas?

10

Apakah ada kebutuhan untuk untuk menjadi tak terbatas untuk diputuskan? $L\subseteq \Sigma^*$

Maksud saya bagaimana jika kita memilih bahasa menjadi versi terbatas terbatas , yaitu , ( ), dengan . Mungkinkah menjadi bahasa yang tidak dapat ditentukan? $L'$ $L\subseteq \Sigma^*$ $|L'|\leq N$ $N \in \mathbb{N}$ $L' \subset L$ $L'$

Saya melihat bahwa ada masalah "Bagaimana memilih kata-kata yang yang harus kita buat aturan untuk memilih yang akan menjadi elemen pertama , semacam bintang Kleene "terbatas" operasi. Tujuannya adalah untuk menemukan bahasa yang tidak dapat diputuskan tanpa perlu set yang tidak terbatas, tetapi saya tidak dapat melihatnya. $N$ $\in$ $L' "$ $N$ $L'$

Catatan EDIT:

Meskipun saya memilih jawaban, banyak jawaban dan semua komentar penting.

formal-languages computability undecidability Hernan_eche
sumber

Tampaknya ada (setidaknya) tiga pertanyaan di sini. Harap berkonsentrasi pada satu dan edit yang lain.

Raphael

Saya menghapus referensi ke set daya karena tidak relevan di sini;

P (S)

$\mathcal{P}(S)$ terbatas hingga dan hanya jika

S

$S$ terbatas.

Raphael

@Raphael Tidak apa-apa, tapi saya menyebutkan power set karena kadang-kadang saya membaca "tidak ada penolakan dari ke , sehingga harus ada bahasa yang tidak dapat ditentukan." $\mathbb{N}$ $\mathcal{P}(\mathbb{N})$ Saya ingin memahami mengapa itu tidak bekerja dengan himpunan terbatas , dengan dengan terbatas, alih-alih membutuhkan , itu sebabnya saya meletakkan

L^{'}

$L'$

| L^{'} | \leq N

$|L'|\leq N$

N

$N$

N

$\mathbb{N}$

P (S)

$\mathcal{P}(S)$

Hernan_eche

1

Sejauh yang saya tahu, keberadaan bahasa yang tidak dapat diputuskan tidak segera mengikuti dari tidak adanya penolakan semacam itu; Anda membutuhkan sedikit lebih banyak. Mengapa, itu akan membuat pertanyaan indah lainnya! Mengapa Anda tidak melanjutkan saja dan menanyakannya? Dari yang itu, Anda harus melihat mengapa argumen tidak terbawa ke bahasa yang terbatas.

Raphael

3

Bahasa yang terbatas adalah decidable, titik, akhir cerita. Ada sejumlah algoritma untuk itu. Jika Anda bersikeras pada model Mesin Turing klasik, itu bisa dilakukan dengan cara itu juga, meskipun kurang tajam. Tidak perlu memanggil automata negara-terbatas atau bahasa reguler atau model otomat lainnya, karena sebenarnya, berlebihan tanpa kejelasan vis-a-vis Mesin Turing.

David Lewis

15

Ya, ada kebutuhan untuk menjadi tak terbatas agar tidak dapat diputuskan. $L$

Untuk menambahkan jawaban Raphael dan Sam, Anda harus memikirkan "decidable" sebagai hal yang dapat dipecahkan oleh program komputer. Program yang diperlukan sangat sederhana, hanya perlu menampilkan "Ya" untuk elemen dalam , atau sebaliknya, katakan tidak. $L$

Jadi, semakin kompleks " " , semakin lama program yang harus Anda tulis. Dengan kata lain, semakin lama program Anda berjalan, Anda dapat memeriksa lebih banyak hal ... Jadi, jika seseorang memberikan bahasa yang terbatas, katakanlah , Anda dapat menulis program berikut: $L$ $L$ $L=\{ a_1, a_2, \ldots, a_n\}$

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

Sekarang, jika seseorang memberi Anda lebih besar (namun terbatas), Anda hanya akan menulis program yang lebih panjang. Ini selalu benar, dan setiap terbatas akan memiliki programnya sendiri. Satu-satunya kasus "menarik" adalah apa yang terjadi ketika tidak terbatas - program Anda tidak dapat tak terbatas. $L$ $L$ $L$

Masalah "ketidakpastian" bahkan lebih menarik: mereka (tanpa batas) yang tidak memiliki program yang berfungsi dengan benar untuk mereka. Kita tahu bahwa bahasa seperti itu harus ada karena ada lebih banyak (tak terbatas) bahasa daripada jumlah program yang terbatas (tapi tidak terbatas) panjangnya. $L$ $L$

Ran G.
sumber

+1 Ini adalah jawaban yang sangat jelas, saya ingin Anda memperluas poin, Anda telah mengatakan "jika seseorang memberi Anda lebih besar (belum terbatas), Anda hanya akan menulis program yang lebih panjang" * tetapi saya pikir kebalikannya, diberikan ** tetap ** terbatas hingga set program , bagaimana jika Anda tidak dapat menulis program yang lebih panjang Saya pikir beberapa imputs set yang terbatas, akan keluar YA, dan beberapa tidak akan . Sebagai , maka beberapa imputs akan sesuai dengan fungsi indikator tetapi * kebanyakan $L$ $P$ $|P|=K$ $\in L$ $\mathcal{P}(P) \gt K$ $\in L$ $P$ tidak akan!, Karena kemungkinan bahasa

2^{K}

$2^K$

> K

$\gt K$ program yang mungkin, maka akan ada masalah yang tidak dapat ditentukan. Apakah aku salah? Mengapa?

Hernan_eche

1

memang, jika Anda membatasi ukuran program ke maka ada paling banyak program berbeda yang dengan benar mengklasifikasikan paling banyak bahasa berbeda (tak terbatas atau tidak). Jadi untuk set program tertentu ada bahasa yang tidak dapat ditentukan dan bahkan yang terbatas. Tetapi ini adalah pernyataan yang lebih lemah, karena Anda hanya mempertimbangkan seperangkat program terbatas (mis. , Anda hanya memiliki 2 program yang mungkin; tentu saja mereka tidak akan dapat berbuat banyak dan akan gagal di hampir setiap bahasa )

| P | = k

$|P|=k$

O (2^{k})

$O(2^k)$

O (2^{k})

$O(2^k)$

| P | = 1

$|P|=1$

L

$L$

Ran G.

terima kasih, saya tahu itu pernyataan yang lebih lemah, tetapi berani bahwa mungkin ada Bahasa yang terbatas dan tidak terbatas, dan saya pikir kasus khusus ini harus dimasukkan dalam jawaban Anda, bagian "Ya, ada kebutuhan untuk L menjadi tak terbatas dalam agar tidak dapat diputuskan. " tampaknya tidak menjadi kebutuhan dalam kondisi tertentu.

Hernan_eche

6

Tidak persis. Istilah "undecidable" memiliki arti khusus: tidak dapat diputuskan oleh mesin Turing standar. Jadi, untuk menjadi undecidable, harus tak terbatas. Yang Anda inginkan hanyalah istilah yang berbeda, yaitu, "tidak dapat dipilih oleh ". Panggil yang terakhir -diklaim. Maka di sana untuk setiap terbatas , tidak perlu bagi untuk menjadi tak terbatas untuk menjadi -disetujui. Hanya saja, jangan bingung (atau menyalahgunakan) dan -diklaim

L

$L$ undecidable

P

$P$

P

$P$

P

$P$

L

$L$

P

$P$ undecidable

P

$P$

Ran G.

10

Saya tidak yakin saya memahami pertanyaan dengan benar tetapi setiap bahasa yang terbatas adalah reguler. Tidak ada bahasa reguler yang tidak dapat diputuskan dan oleh karena itu tidak ada bahasa terbatas yang tidak dapat diputuskan. Semua pernyataan ini terkenal dan bukti dapat ditemukan di Hopcroft dan Ullman .

Sam Jones
sumber

8

Jika bahasa Anda terbatas, Anda dapat melakukan pencarian tabel pada tabel hardcode yang berisi semua kata dalam . Ini canggung untuk ditulis sebagai mesin Turing, tetapi dalam model lain yang setara cukup jelas. $L'$ $L'$

Bahkan, automata terbatas sudah cukup. Buat otomat untuk sebagai berikut: $L'$

Untuk setiap , buat rantai linear status yang menerima . $w \in L'$ $w$
Buat status awal baru . $q_0$
Hubungkan ke status awal semua automata yang dibuat di 1. dengan -transitions. $q_0$ $\varepsilon$

Otomat yang dikonstruksi demikian jelas menerima . Oleh karena itu, teratur dan dengan itu dapat dihitung (oleh ). $L'$ $L'$ $\mathrm{REG} \subsetneq \mathrm{RE}$

Perhatikan bahwa beberapa alasan berlaku untuk co-finite , yaitu ; Anda hanya meng-hardcode elemen-elemen yang tidak ada di . $L'$ $\big|\overline{L'}\big| < \infty$ $L'$

Raphael
sumber

2

Untuk menjadi sama sekali menarik (untuk tujuan berpikir tentang komputabilitas) masalah keputusan harus memiliki banyak jawaban "ya" dan banyak sekali jawaban "tidak". Masalah keputusan seperti itu sesuai dengan bahasa yang mengandung banyak string tanpa batas atas alfabet mereka dan juga mengecualikan banyak string yang tak terbatas atas alfabet mereka.

Hal lain sepele yang dapat dikodekan hanya dalam jumlah terbatas informasi (paling buruk hanya daftar besar string baik dalam atau tidak dalam bahasa), dan karenanya dapat dihitung dengan DFA sederhana / ekspresi reguler. Saya berharap semestinya jelas bahwa untuk setiap daftar string yang terbatas Anda dapat segera menuliskan ekspresi reguler yang hanya ATAU semua string.

Sebuah lelucon dari dosen Teori Komputasi saya adalah bahwa masalah "apakah Tuhan ada?" dapat dihitung - itu dihitung oleh mesin yang langsung menerima, atau mesin yang langsung menolak; kita tidak tahu yang mana!

Ben
sumber

Apakah ada bahasa terbatas dari kata-kata terbatas?

Jawaban: