Operasi apa yang perlu dilakukan untuk melakukan perhitungan analog sewenang-wenang ? Apakah penambahan, pengurangan, penggandaan, dan pembagian cukup? Juga, apakah ada yang tahu persis masalah apa yang dapat ditelusuri menggunakan perhitungan analog, tetapi tidak dengan
Apakah ada mesin Turing yang menghentikan semua input tetapi properti itu tidak dapat dibuktikan karena alasan tertentu? Saya bertanya-tanya apakah pertanyaan ini telah dipelajari. Catatan, "tidak dapat dibuktikan" dapat berarti sistem bukti "terbatas" (yang dalam arti lemah berpikir jawabannya...
Saya mulai membaca buku tentang Kompleksitas Komputasi dan Mesin Turing. Berikut ini kutipannya: Algoritma (yaitu, mesin) dapat direpresentasikan sebagai string bit setelah kami memutuskan beberapa pengkodean kanonik. Pernyataan ini diberikan sebagai fakta sederhana, tetapi saya tidak bisa...
Dalam pertanyaan ini kami hanya mempertimbangkan mesin Turing yang berhenti pada semua input. Jika k∈Nk∈Nk \in \mathbb{N} maka oleh kita menunjukkan mesin Turing yang kodenya adalah . kTkTkT_kkkk Pertimbangkan fungsi berikut s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y) =...
Diberikan bahasa dan , katakanlah bahwa gabungan tidak ambigu jika untuk semua kata , ada tepat satu dekomposisi dengan dan , dan ambigu sebaliknya. (Saya tidak tahu apakah ada istilah yang mapan untuk properti ini — hal yang sulit untuk dicari!) Sebagai contoh sepele, gabungan dari dengan dirinya...
Perhatikan bahwa ini adalah pertanyaan yang terkait dengan belajar di kursus CS di universitas, BUKAN pekerjaan rumah dan dapat ditemukan di sini di bawah ujian Musim Gugur 20112. Inilah dua pertanyaan yang saya lihat dari ujian sebelumnya. Mereka tampaknya terkait, yang pertama: Membiarkan...
Masalah apakah dua automat pushdown mengenali bahasa yang sama tidak dapat diputuskan. Masalah apakah automat pushdown mengenali bahasa kosong dapat diputuskan, maka itu juga dapat memutuskan apakah ia mengenali bahasa yang terbatas. Tidak dapat diputuskan apakah bahasa yang diterima oleh otomat...
Tidak ada solusi analitik umum untuk masalah n-body yang dapat menghasilkan fungsi analitik yang dapat digunakan untuk memberikan status sistem n-body pada waktu acak t dengan presisi yang tepat. Namun, ada beberapa kasus khusus dari sistem n-body yang fungsi analitiknya diketahui. Dalam banyak...
Saya menggunakan komputer digital untuk menulis pesan ini. Mesin semacam itu memiliki properti yang, jika Anda pikirkan, sebenarnya sangat luar biasa: Ini adalah mesin yang, jika diprogram dengan tepat, dapat melakukan perhitungan yang memungkinkan . Tentu saja, mesin hitung dari satu jenis atau...
Mesin penghitung dengan dua atau lebih penghitung biasanya ditunjukkan setara dengan mesin Turing dalam kursus tentang teori perhitungan. Namun, saya belum melihat analisis formal yang bahasa dapat dikenali oleh mesin satu-counter. Apakah bahasa-bahasa ini setara dengan bahasa bebas konteks...
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...
Dalam sebuah ceramah seorang profesor menyebutkan bahwa komputer modern tidak memiliki kekuatan komputasi sebanyak mesin Turing karena mereka tidak memiliki memori tak terbatas, dan karena tidak ada komputer yang dapat memiliki memori tak terbatas, mesin Turing karenanya tidak dapat dicapai dan...
Suatu himpunan dapat dihitung jika ia memiliki bilangan bijih dengan bilangan asli, dan dapat dihitung (ce) jika ada algoritma yang menyebutkan anggotanya. Setiap himpunan enumerable komputabel yang tidak terbatas harus dihitung karena kita dapat membangun suatu penghitungan dari...
Diberi bahasa , tentukan panjang himpunan L sebagai himpunan panjang kata dalam L : L S ( L ) = { | kamu | ∣ u ∈ L }L.LLL.LLL.LLL S (L)={ | kamu | ∣u∈L}LS(L)={|u|∣u∈L}\mathrm{LS}(L) = \{|u| \mid u \in L \} Set bilangan bulat mana yang dapat menjadi set panjang bahasa...
Aku bertanya-tanya bagaimana datang bahwa bahasa berikut ini di .RR\mathrm R LM1={⟨M2⟩∣∣M2 is a TM, and L(M1)=L(M2), and |⟨M1⟩|>|⟨M2⟩|}LM1={⟨M2⟩|M2 is a TM, and L(M1)=L(M2), and |⟨M1⟩|>|⟨M2⟩|}L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and } L(M_1)=L(M_2), \text{ and }...
Saya memiliki pertanyaan-pertanyaan ini dari ujian lama yang saya coba selesaikan. Untuk setiap masalah, input adalah encoding dari beberapa Turing mesin .MMM Untuk bilangan bulat , dan tiga masalah berikut:c>1c>1c>1 Benarkah bahwa untuk setiap input , M tidak lulus posisi saat...
Saya ingin tahu apakah masalah berikut ini dapat ditentukan: Instance: NFA A dengan n state Pertanyaan: Apakah ada beberapa bilangan prima p sehingga A menerima beberapa untaian panjang p. Keyakinan saya adalah bahwa masalah ini tidak dapat diputuskan, tetapi saya tidak dapat membuktikannya....
Bahasa seperti adalah bawah banyak-satu reduksi. Sangat sepele untuk melihat bahwa memiliki masalah. S. Schmitz [1] mempertimbangkan beberapa kelas antara dan . Mereka menghadirkan masalah lengkap untuk kelas-kelas ini di bawah pengurangan yang dibuat
Saya sedang mencari masalah terbuka yang mudah dan menarik untuk dinyatakan dalam komputabilitas (dapat dimengerti oleh mahasiswa sarjana yang mengambil kursus pertama mereka dalam komputabilitas) untuk memberikan contoh masalah terbuka (dan jelas saya ingin para siswa dapat memahami masalah tanpa...
Jika sebenarnya sama dengan , bagaimana hal ini akan meningkatkan algoritma kami menjadi faktor integer lebih cepat. Dengan kata lain, wawasan seperti apa yang akan diberikan fakta ini dalam memahami faktorisasi bilangan bulat lebih baik?PP{\sf P}N PNP{\sf