Jakie są granice obliczeń w tym wszechświecie?

17

Rozumiem, że kompletność Turinga wymaga nieograniczonej pamięci i nieograniczonego czasu.

Jednak w tej usłudze jest skończona ilość atomów, co ogranicza pamięć. Na przykład, chociaż jest irracjonalne, nie ma sposobu na przechowywanie więcej niż pewnej liczby cyfr, nawet jeśli do tego celu zostały użyte wszystkie atomy we wszechświecie.π

Jakie są zatem granice obliczalności zaimplementowanej maszyny Turinga (która mogłaby wykorzystać wszystkie zasoby wszechświata, ale nie więcej) w oparciu o granice wszechświata? Jaka jest maksymalna liczba cyfr ? Czy są jakieś artykuły na ten temat, które mogą być interesujące do przeczytania?π

Dobra osoba
źródło
1
Prawdopodobnie powiązany temat: Czy komputer może symulować się jako część symulowanego świata .
MS Dousti
7
Jest zabawny esej Scott Aaronson na ten temat: scottaaronson.com/writings/finite.html
Artem Kaznatcheev
2
Być może zainteresuje Cię dyskusja wokół tego pytania . Yarosloav Bulatov zamieścił link do popularnej wersji naukowej gazety Lloyda Petera Shora, do którego link znajduje się poniżej, ale niestety link wydaje się teraz zepsuty. Czytałem wtedy ten artykuł, ale go nie zapisałem i nie pamiętam dokładnego tytułu.
Aaron Sterling

Odpowiedzi:

34

Seth Lloyd ma artykuł na ten temat. Potrzebujesz energii do obliczeń, ale jeśli włożysz zbyt dużo energii w mały region, tworzy się czarna dziura. Spowalnia to czas (co powoduje, że obliczenia są stosunkowo dłuższe), a wszelkie obliczenia wykonane we wnętrzu czarnej dziury są marnowane, ponieważ wyników nie można wyodrębnić z czarnej dziury i użyć. Seth oblicza granice możliwej ilości obliczeń i pokazuje, że dla niektórych miar obliczeń najbardziej intensywnym obliczeniowo środowiskiem we wszechświecie byłoby otoczenie czarnej dziury.

Peter Shor
źródło
10
@AaronRoth Utknąłem w czarnej dziurze. Zaakceptowane teraz.
Good Person