Berapa batas perhitungan di alam semesta ini?

17

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?π

Orang yang baik
sumber
7
Ada yang menyenangkan esai oleh Scott Aaronson hal ini: scottaaronson.com/writings/finite.html
Artem Kaznatcheev
2
Anda mungkin tertarik dengan diskusi seputar pertanyaan ini . Yarosloav Bulatov memposting tautan ke versi sains populer dari makalah Lloyd yang dikaitkan dengan Peter Shor di bawah, tetapi, sayangnya, tautan tersebut tampaknya rusak sekarang. Saya membaca makalah itu pada saat itu, tetapi tidak menyimpannya, dan tidak ingat judulnya.
Aaron Sterling

Jawaban:

34

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.

Peter Shor
sumber
10
@ Harun, saya terjebak di lubang hitam. Diterima sekarang
Orang Baik