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 di alam semesta digunakan untuk tujuan ini.
Lalu apa batas kemampuan komputasi dari mesin Turing yang diimplementasikan (yang dapat menggunakan semua sumber daya alam semesta tetapi tidak lebih) berdasarkan pada batas-batas alam semesta? Berapa jumlah maksimum digit ? Apakah ada makalah tentang hal ini yang mungkin menarik untuk dibaca?
computability
upper-bounds
Orang yang baik
sumber
sumber
Jawaban:
Seth Lloyd memiliki makalah tentang masalah ini. Anda perlu energi untuk menghitung, tetapi jika Anda memasukkan terlalu banyak energi ke wilayah kecil, itu membentuk lubang hitam. Ini memperlambat waktu (membuat waktu yang dibutuhkan untuk menyelesaikannya relatif lebih lama), dan setiap perhitungan yang dilakukan di bagian dalam lubang hitam terbuang sia-sia, karena hasilnya tidak dapat diekstraksi dari lubang hitam dan digunakan. Seth menghitung batas jumlah komputasi yang mungkin, dan menunjukkan bahwa untuk beberapa ukuran komputasi, lingkungan paling intensif komputasi yang mungkin ada di alam semesta adalah lingkungan sekitar lubang hitam.
sumber