Saya memahami bukti ketidaktentuan masalah penghentian (diberikan misalnya dalam buku teks Papadimitriou), berdasarkan diagonalisasi. Sementara buktinya meyakinkan (saya mengerti setiap langkahnya), itu tidak intuitif bagi saya dalam arti bahwa saya tidak melihat bagaimana seseorang akan...
Saat ini saya sedang membaca buku tentang algoritma dan kompleksitas. Saat ini saya sedang membaca tentang fungsi yang dapat dikomputasi dan yang tidak dapat dikomputasi, dan buku saya menyatakan bahwa ada lebih banyak fungsi yang tidak dapat dikomputasi daripada yang dapat dikomputasi, bahkan...
Tesis Gereja-Turing menyatakan bahwa segala sesuatu yang secara fisik dapat dihitung, dapat dihitung pada Mesin Turing. Makalah "Komputasi analog melalui jaringan saraf" (Siegelmannn dan Sontag, Theoretical Computer Science , 131: 331-360, 1994; PDF ) mengklaim bahwa jaring saraf dari bentuk...
Kami belajar tentang konsep enumerasi fungsi. Dalam praktiknya, mereka berhubungan dengan bahasa pemrograman. Dalam komentar yang lewat, profesor menyebutkan bahwa kelas semua fungsi total (yaitu fungsi yang selalu berakhir untuk setiap input) tidak dapat dihitung. Itu berarti bahwa kita tidak...
Saya menemukan pernyataan di bawah ini oleh Alan M. Turing di sini : "Pandangan bahwa mesin tidak dapat menimbulkan kejutan adalah karena, saya percaya, pada kekeliruan yang menjadi fokus para filsuf dan matematikawan. Ini adalah asumsi bahwa segera setelah sebuah fakta disajikan di benak semua...
Setiap masalah yang tidak dapat dipastikan yang saya ketahui termasuk dalam salah satu kategori berikut: Masalah yang tidak dapat dipastikan karena diagonalisasi (referensi diri tidak langsung). Masalah-masalah ini, seperti masalah penghentian, tidak dapat diputuskan karena Anda dapat menggunakan...
Apakah ada program yang dapat 'menerjemahkan' kode sumber antara dua bahasa (dengan asumsi penerjemah memiliki akses ke perpustakaan yang diperlukan)? Jika ada, bagaimana cara kerjanya (teknik yang digunakan, pengetahuan yang dibutuhkan, dll)? Bagaimana mereka layak dibangun? Jika tidak,...
Combinator titik tetap FIX (alias combinator Y) dalam kalkulus lambda (tidak diketik) ( ) didefinisikan sebagai:λλ\lambda FIX≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. x~x~y)) Saya...
Wikipedia serta sumber lain yang saya temukan daftar voidtipe C sebagai tipe unit sebagai lawan dari tipe kosong. Saya menemukan ini membingungkan karena menurut saya voidlebih cocok dengan definisi tipe kosong / bawah. Tidak ada nilai yang dihuni void, sejauh yang saya tahu. Suatu fungsi dengan...
Masalah penghentian menyatakan tidak ada algoritma yang akan menentukan apakah program yang diberikan berhenti. Sebagai konsekuensinya, harus ada program yang tidak dapat kami katakan apakah mereka berakhir atau tidak. Apa contoh paling sederhana (paling kecil) dari program semacam...
Catatan, sementara saya tahu cara memprogram, saya cukup pemula dalam teori CS. Menurut jawaban ini Kelengkapan Turing adalah konsep abstrak dari kemampuan komputasi. Jika suatu bahasa Turing lengkap, maka ia mampu melakukan perhitungan apa pun yang bisa dilakukan bahasa lengkap Turing...
Jelas tidak ada masalah yang tidak dapat dipastikan dalam NP. Namun, menurut Wikipedia : NP adalah himpunan semua masalah keputusan yang contohnya adalah "ya" memiliki [.. bukti yang] dapat diverifikasi dalam waktu polinomial oleh mesin Turing deterministik. [...] Suatu masalah dikatakan...
Saya mengalami kesulitan memahami bukti tentang keraguan atas Masalah yang Menghambat. Jika kembali apakah program yang perhentian pada input b , mengapa kita harus melewati kode P untuk kedua a dan b ?H(a,b)H(a,b)H(a,b)aaabbbPPPaaabbb Mengapa kita tidak bisa memberi makan dengan P dan beberapa...
Pertanyaan ini dimigrasikan dari Theoretical Computer Science Stack Exchange karena dapat dijawab di Computer Science Stack Exchange. Bermigrasi 6 tahun yang lalu . Saya telah menemukan banyak definisi bahasa recursive dan recumerif enumerable. Tapi saya tidak bisa
Pertanyaan ini dimigrasikan dari Theoretical Computer Science Stack Exchange karena dapat dijawab di Computer Science Stack Exchange. Bermigrasi 7 tahun yang lalu . Saya hanya punya pertanyaan menarik ini. Apa fungsi yang paling cepat diketahui manusia? Apakah ini
Dalam teori komputabilitas, fungsi yang dapat dihitung juga disebut fungsi rekursif. Setidaknya pada pandangan pertama, mereka tidak memiliki kesamaan apa pun dengan apa yang Anda sebut "rekursif" dalam pemrograman sehari-hari (yaitu, fungsi yang menyebut dirinya sendiri). Apa arti sebenarnya dari...
Pertanyaan ini dimigrasikan dari Theoretical Computer Science Stack Exchange karena dapat dijawab di Computer Science Stack Exchange. Bermigrasi 7 tahun yang lalu . "Alan Turing membuktikan pada tahun 1936 bahwa algoritma umum untuk memecahkan masalah penghentian untuk...
Saya telah mempelajari sesuatu tentang Kompleksitas Kolmogorov , membaca beberapa artikel dan buku dari Vitanyi dan Li dan menggunakan konsep Normalized Compression Distance untuk memverifikasi stilometri penulis (mengidentifikasi bagaimana setiap penulis menulis beberapa teks dan dokumen kelompok...
Apakah ada bahasa "alami" yang tidak dapat diputuskan? oleh "alami" Maksudku bahasa yang didefinisikan secara langsung oleh properti string, dan bukan melalui mesin dan setara mereka. Dengan kata lain, jika bahasanya mirip mana adalah TM, DFA (atau regular-exp), PDA (atau tata bahasa), dll.,...
Mungkin pemahaman saya yang terbatas tentang subjek ini tidak benar, tetapi sejauh ini yang saya mengerti: Pemrograman fungsional didasarkan dari Lambda Calculus, yang dirumuskan oleh Gereja Alonzo. Pemrograman imperatif didasarkan pada model mesin Turing, yang dibuat oleh Alan Turing, siswa...