Ile mocy obliczeniowej mieści się w centymetr sześcienny?

To pytanie stanowi odpowiedź na pytanie o algorytmy DNA zadane przez Aaditę Mehrę .

W komentarzach Joe Fitzsimmons powiedział częściowo:

Promień układu musi być skalowany proporcjonalnie do masy, aby tego uniknąć. Moc obliczeniowa jest skalowana co najwyżej liniowo w masie. Zatem twoja wykładnicza ilość maszyn ma wykładniczy promień. Ponieważ nie można zasygnalizować szybciej niż światło, sygnał z jednej strony na drugą zajmuje wykładniczo długi czas, aby dotrzeć do drugiej strony, więc jeśli wszystkie maszyny przyczynią się do odpowiedzi, niemożliwe jest rozwiązanie problemu w sposób mniejszy niż wykładniczy czas.

Moje pytanie składa się z dwóch części.

(1) Jaki jest najlepszy sposób / sposoby sformalizowania stwierdzenia, takiego jak: „Moc obliczeniowa skaluje się co najwyżej liniowo w masie”? Czy to stwierdzenie naprawdę nie nadaje się do debaty?

(2) Załóżmy, że stwierdzenie jest prawdziwe. Mimo to, natura mogłaby już dokonać wykładniczej obróbki wstępnej, z której moglibyśmy skorzystać, na przykład stworzenia ewolucji systemów wizyjnych poprzez „randomizację brutalnej siły”.

Słyszałem i czytałem sporo miękkich (pseudonaukowych) odpowiedzi na tego rodzaju pytania i byłbym wdzięczny za wszelkie odpowiedzi tutaj, ale najbardziej interesuje mnie, w jaki sposób (1) i (2) można przekształcić w dyscyplinie TCS.

Oświadczenie, które złożyłem, nie było szczególnie dobrze napisane. Miałem na myśli kombinację twierdzenia Margolusa-Levitina (która daje minimalny czas na przejście między dwoma stanami ortogonalnymi, a zatem niższą granicę czasu potrzebnego do wykonania bramki) i promienia Schwarzschilda (który daje minimalny promień układ pewnej stałej energii przed utworzeniem czarnej dziury). Połączenie tych dwóch prowadzi do górnej granicy liczby bramek, które można wykonać w ustalonym obszarze czasoprzestrzeni. Możesz myśleć o tym jak o maksymalnej liczbie bramek na jednostkę czasu, którą można wykonać.

Pomysł połączenia tych dwóch twierdzeń pochodzi od Setha Lloyda, który stosuje takie podejście, aby pokazać ograniczenia mocy obliczeniowej wszechświata ( link ). Ma także inny artykuł, w którym patrzy na maksymalną wydajność, jaką można uzyskać za pomocą 1 kg komputera o pojemności 1 litra (coś, co nazywa najlepszym laptopem i które jest prawie dokładnie twoim pytaniem). Zobacz arXiv . Uzyskuje limit$10^{51}$ operacji na sekundę $10^{31}$bitów Ze względu na skończony wiek wszechświata i skończoną prędkość światła, w połączeniu z wynikami Lloyda, uzyskujesz stałą górną granicę podczas wstępnego przetwarzania.