Saya mengerti bahwa sebagian besar masalah sepele jika tersedia oracle yang berhenti (atau, saya pikir setara, hiper-komputasi). Namun, menerapkan argumen yang menunjukkan Masalah Henti tidak mungkin untuk mesin Turing juga menunjukkan bahwa tidak mungkin bagi oracle Turing + untuk memutuskan...
Saya sedang membaca jawaban untuk pertanyaan baru-baru ini, dan semacam pemikiran fana yang aneh muncul di benak saya. Saya bertanya ini mungkin mengkhianati bahwa teori saya kurang serius (sebagian besar benar) atau terlalu dini bagi saya untuk membaca situs ini. Sekarang, dengan disclaimer keluar...
Dalam masalah penghentian, kami tertarik jika ada mesin Turing yang dapat mengetahui apakah mesin Turing M yang diberikan berhenti atau tidak pada input yang diberikan i . Biasanya, buktinya mulai dengan menganggap T seperti itu ada. Kemudian, kami mempertimbangkan kasus di mana kami membatasi i...
Saya sudah mencoba mencari tahu apakah masalah penghentian dapat dipilih untuk automata seluler satu dimensi 3-simbol. Definisi Biarkan menunjukkan konfigurasi sistem pada langkah waktu i . Secara lebih formal f : A ∗ × N → A ∗ , di mana A adalah
Dalam Chaitin Meta Math! The Quest For Omega , ia secara singkat berbicara tentang Masalah ke-10 Hilbert. Dia kemudian mengatakan bahwa Persamaan Diophantine dapat diubah menjadi dua polinomial yang sama dengan koefisien bilangan bulat positif: .p = 0p = 0p=0p=0p = 0⟺hal1= p2p=0⟺p1=p2p=0 \iff p_1 =...
Pertanyaan ini muncul pada saya tentang masalah penghentian dan saya tidak dapat menemukan jawaban online yang bagus, bertanya-tanya apakah ada yang bisa membantu. Apakah mungkin bahwa masalah penghentian dapat diputuskan untuk setiap TM pada input apa pun asalkan inputnya bukan TM itu sendiri?...
Menurut sumber ini, konstanta Chaitin ΩΩ\Omega itu normal. Setiap probabilitas penghentian adalah bilangan real normal dan transendental yang tidak dapat dihitung, yang berarti bahwa tidak ada algoritma untuk menghitung digitnya. Memang, setiap probabilitas penghentian adalah acak Martin-Löf,...
Dengan tesis Church-Turing, mustahil untuk merancang algoritma untuk memutuskan masalah penghentian. Apakah kata algoritma dalam konteks ini termasuk kecerdasan buatan atau tidak, yaitu apakah tesis Church-Turing juga berlaku untuk kecerdasan buatan? Apakah mungkin untuk merancang sistem...
Sepengetahuan saya, menghentikan masalah bertanya apakah ada program yang memutuskan apakah suatu program sedang diuji, diberi beberapa data input (tidak peduli program apa itu, atau data input apa yang kami berikan) akan berakhir atau tidak. Jawaban untuk masalah ini adalah 'tidak'. Dengan kata...
Saya mencoba untuk menemukan cara untuk menjelaskan ide bukti Masalah terputus dengan cara yang dapat diakses (untuk mahasiswa CS sarjana). Argumen paling sederhana yang saya temukan adalah argumen ini ; inilah gaya perawatan yang saya tuju. Namun, referensi-diri (khususnya, memeriksa apakah suatu...