Saya mengerti bahwa kelengkapan Turing membutuhkan memori tanpa batas dan waktu tanpa batas. Namun ada sejumlah atom dalam layanan ini sehingga membuat memori dibatasi. Sebagai contoh meskipun tidak rasional, tidak ada cara untuk menyimpan lebih dari jumlah digit tertentu bahkan jika semua atom...
Katakanlah Anda membangun komputer yang akan menghitung keadaan semua atom di Semesta pada titik waktu tertentu di masa depan. Karena Universe, menurut definisi, adalah segala sesuatu yang ada (dan apa pun yang berinteraksi dengan yang lain), ia juga termasuk komputer yang Anda bangun. Bisakah Anda...
Komputasi berlebihan mengacu pada model komputasi yang tidak mungkin untuk disimulasikan menggunakan mesin Turing. (Hypercomputer belum tentu dapat direalisasikan secara fisik!) Beberapa hypercomputer memiliki akses ke sumber daya yang memungkinkan Masalah Pemutusan untuk mesin Turing standar dapat...
Labirin fraktal adalah labirin yang berisi salinan dirinya sendiri. Misalnya, yang berikut oleh Mark JP Wolf dari artikel ini : Mulailah di MINUS dan lanjutkan ke PLUS. Saat Anda memasukkan salinan labirin yang lebih kecil, pastikan untuk mencatat nama surat salinan itu, karena Anda harus...
Saya mencari kombinator universal terkecil yang mungkin , diukur dengan jumlah abstraksi dan aplikasi yang diperlukan untuk menentukan kombinator tersebut dalam kalkulus lambda . Contoh-contoh kombinator universal meliputi: ukuran 23: λf.f (fS (KKKI)) K ukuran 18: λf.f (fS (KK)) K ukuran 14:...
Banyak teorema dan "paradoks" - diagonalisasi Cantor, ketidakpastian hatling, tidak dihargai kompleksitas Kolmogorov, Gödel Incompleteness, Chaitin Incompleteness, paradox Russell, dll. - semua pada dasarnya memiliki bukti yang sama dengan diagonisasi (perhatikan bahwa ini lebih spesifik daripada...
Apakah ada teorema umum yang akan menyatakan, dengan sanitasi yang tepat, bahwa hasil yang paling diketahui mengenai penggunaan bilangan real sebenarnya dapat digunakan ketika mempertimbangkan hanya real yang dapat dihitung? Atau adakah karakterisasi hasil yang tepat yang tetap valid ketika hanya...
Salah satu hal menakjubkan tentang ilmu komputer adalah bahwa implementasi fisik dalam beberapa hal "tidak relevan". Orang-orang telah berhasil membangun komputer dari beberapa substrat yang berbeda - relay, tabung hampa udara, transistor diskrit, dll. Orang mungkin akan segera berhasil membangun...
Saya mencari jawaban pasti untuk pertanyaan judul. Apakah ada seperangkat aturan yang menerjemahkan program apa pun ke dalam konfigurasi potongan terbatas di papan infinite, sehingga jika hitam dan putih hanya memainkan gerakan hukum, permainan berakhir pada waktu terbatas jika program...
Bahasa apa pun yang tidak lengkap Turing tidak dapat menulis penerjemah untuk itu sendiri. Saya tidak tahu di mana saya membaca itu tetapi saya telah melihatnya digunakan beberapa kali. Sepertinya ini memunculkan semacam bahasa "Turing" non-Turing lengkap; satu-satunya yang hanya bisaditafsirkan...
( PEMBARUAN : pertanyaan yang terbentuk lebih baik diajukan di sini karena komentar untuk jawaban yang diterima di bawah menunjukkan bahwa pertanyaan ini tidak didefinisikan dengan baik) Bukti klasik ketidakmungkinan masalah berhenti tergantung pada menunjukkan kontradiksi ketika mencoba...
Bisakah Anda menunjukkan bagaimana membangun fungsi Ackerman (sebenarnya saya tertarik pada versi yang diusulkan oleh Rózsa Péter dan Raphael Robinson) melalui operator standar rekursif mu? Saya mencoba makalah asli oleh Péter dan Robinson, tetapi makalah Péter menggunakan bahasa yang berbeda dari...
Kami mengatakan bahwa Mesin Turing adalah fana jika M berhenti untuk setiap konfigurasi awal (khususnya, konten rekaman dan keadaan awal dapat arbitrer). Apakah setiap bahasa rekursif dikenali oleh Mesin Turing fana? (yaitu jika ada TM yang menerima L , ada juga TM fana yang menerimaMMMMMMLLL...
Pertanyaan ini juga telah diposting di Math.SE, /math/1002540/fixed-points-in-computability-nd-logic Saya harap tidak apa-apa untuk memposting di sini. Jika tidak, atau terlalu mendasar untuk CS.SE, tolong beri tahu saya dan saya akan menghapusnya. Saya ingin lebih memahami hubungan antara...
Diberi bahasa L yang didefinisikan oleh Turing Machine yang memutuskannya, apakah mungkin menentukan secara algoritmik apakah L terletak pada
Sudah lama diketahui bahwa, mengingat gelar Turing apa pun, ada grup yang dipresentasikan secara halus yang masalah kata-katanya ada di tingkat itu. Pertanyaan saya adalah apakah hal yang sama berlaku untuk waktu polinomial Turing derajat sewenang-wenang . Secara khusus, diberikan himpunan...
Greg Egan dalam fiksinya "Dark Integers" (cerita tentang dua alam semesta dengan dua matematika berbeda yang berkomunikasi dengan membuktikan teorema tentang ketidakkonsistenan dalam aritmatika) mengklaim bahwa adalah mungkin untuk membangun komputer tujuan umum hanya pada router internet yang ada...
Teorema Rice menyatakan bahwa setiap properti nontrivial dari set yang dikenali oleh beberapa mesin Turing tidak dapat diputuskan. Saya mencari teorema tipe-Beras kompleksitas-yang memberi tahu kita sifat nontrivial dari set NP mana yang tidak bisa
Dua makalah yang akan saya sertakan adalah: D. Kozen, "Pengindeksan kelas subkursif" , STOC, 1978. R. Ladner, "Tentang Struktur Pengurangan Waktu Polinomial" , JACM,
Saya tertarik pada masalah "terdekat" (dan "paling kompleks") dengan dugaan Collatz yang telah berhasil diselesaikan (yang menurut Erdos terkenal "matematika belum matang untuk masalah seperti itu"). Telah terbukti bahwa kelas masalah "Collatz-like" tidak dapat diputuskan. Namun, masalah yang...