Apakah ada bahasa yang dapat diperhitungkan Turing yang tak terhitung?

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

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.

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.$\omega$

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.$\omega$

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.$\Sigma^\omega$$\Sigma$$\Sigma = \{0,1\}$$\Sigma^\mathbb{N} = 2^\mathbb{N}$$2^{2^\mathbb{N}}$

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 .$M$$L \in \Sigma^*$$N$$x\in \Sigma^\omega$$M$$x$$N$$x$$L$

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.$k\in \mathbb{N}$$k$$k$$3$$6$

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

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.$L_i$$L = \cup_i L_i$$L$$L$$L$

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

5. $k$$k$

$x \mapsto \lg x$$x$$\lg x$ untuk kita.

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