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?
computability
upper-bounds
Dobra osoba
źródło
źródło
Odpowiedzi:
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.
źródło