Pertanyaan tentang mesin Turing, model teoritis perhitungan mekanis yang mampu mensimulasikan program komputer apa pun.
Saya seorang sarjana CS. Saya mengerti bagaimana Turing menghasilkan mesin abstraknya (memodelkan seseorang yang melakukan perhitungan), tetapi bagi saya tampaknya adalah abstraksi yang canggung dan tidak masuk akal. Mengapa kita mempertimbangkan "pita", dan kepala mesin menulis simbol, mengubah...
Kita tahu masalah penghentian (pada Mesin Turing) tidak dapat dipastikan untuk Mesin Turing. Apakah ada penelitian tentang seberapa baik pikiran manusia dapat mengatasi masalah ini, mungkin dibantu oleh Turing Machines atau komputer tujuan umum? Catatan : Jelas, dalam arti yang paling ketat, Anda...
Apakah ada set konstruksi bahasa pemrograman dalam bahasa pemrograman agar Turing Lengkap? Dari apa yang saya dapat katakan dari wikipedia , bahasa perlu mendukung rekursi, atau, tampaknya, harus dapat berjalan tanpa berhenti. Apakah ini semua yang ada untuk
Saya setuju bahwa Mesin Turing dapat melakukan "semua kemungkinan masalah matematika". Tapi itu karena itu hanya representasi mesin dari suatu algoritma: pertama lakukan ini, kemudian lakukan itu, akhirnya keluaran itu. Maksud saya apa pun yang dapat dipecahkan dapat diwakili oleh suatu algoritma...
Dalam perhitungan kuantum, apa model yang setara dari mesin Turing? Sangat jelas bagi saya bagaimana sirkuit kuantum dapat dibangun dari gerbang kuantum, tetapi bagaimana kita dapat mendefinisikan mesin Turing kuantum (QTM) yang benar-benar dapat mengambil manfaat dari efek kuantum, yaitu, bekerja...
Dalam jawaban ini disebutkan Bahasa reguler dapat dikenali oleh otomat terbatas. Bahasa bebas konteks memerlukan tumpukan, dan bahasa sensitif konteks membutuhkan dua tumpukan (yang setara dengan mengatakan itu memerlukan mesin Turing penuh) . Saya ingin tahu tentang kebenaran bagian yang...
Apakah ada mesin teoritis yang melebihi kemampuan mesin Turing di setidaknya beberapa
Saya melihat bahwa sebagian besar definisi Turing-complete adalah tautologis. Misalnya jika Anda Google "apa artinya menjadi Turing lengkap", Anda mendapatkan: Komputer Turing lengkap jika dapat menyelesaikan masalah apa pun yang dapat dilakukan mesin Turing ... Sementara itu didefinisikan...
Alan Turing mengusulkan model untuk mesin (Turing Machine, TM) yang menghitung (angka, fungsi, dll.) Dan membuktikan Teorema Henti . TM adalah konsep abstrak dari mesin (atau mesin jika Anda suka). Teorema Penghentian adalah hasil ketidakmungkinan. Mesin Carnot (CE) adalah konsep abstrak dari...
Saya telah melalui diskusi tentang pertanyaan Bagaimana cara mendefinisikan mesin Turing kuantum? dan saya merasa bahwa TM kuantum dan TM nondetermistic adalah satu dan sama. Jawaban untuk pertanyaan lain tidak menyentuh itu. Apakah kedua model ini satu dan sama? Jika tidak, Apa perbedaan antara...
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...
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...
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...
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...
Saya seorang insinyur listrik, dan hanya memiliki satu kursus CS di perguruan tinggi 26 tahun yang lalu. Namun, saya juga pengguna setia Mathematica. Saya merasa bahwa Mesin Turing sangat penting dalam ilmu komputer. Apakah kepentingannya hanya dalam teori ilmu komputer? Jika ada implikasi /...
Baru-baru ini di kelas CS saya, saya diperkenalkan dengan Mesin Turing. Setelah kelas, saya menghabiskan lebih dari 2 jam mencoba mencari tahu apa hubungan antara kaset dan mesin. Saya sama sekali tidak menyadari keberadaan kaset komputer atau bagaimana kaset dan mesin berinteraksi sampai hari...
Saya sedang melakukan presentasi tentang mesin Turing dan saya ingin memberikan latar belakang tentang FSM sebelum memperkenalkan Mesin Turing. Masalahnya adalah, saya benar-benar tidak tahu apa yang SANGAT berbeda satu sama lain. Inilah yang saya tahu berbeda: FSM memiliki status berurutan...
Dengan hanya mempertimbangkan alfabet , string yang dapat diberikan sebagai input ke mesin Turing berasal dari himpunan Σ ∗ . Tetapi apakah masuk akal untuk input menjadi string biner yang tak terbatas? Sebagai contoh jika mesin Turing menerima semua string dimulai dengan 0, apakah string biner nol...
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...