Obliczenia nieskończone w czasie skończonym

Jest to prawdopodobnie głupia myśl, ale załóżmy, że mamy komputer, który jest zaprogramowany do wykonywania nieskończonej sekwencji obliczeń i załóżmy, że wykonanie obliczenia zajmuje sekundy sekundę. Następnie ten komputer może wykonać nieskończoną liczbę obliczeń w skończonym czasie. $i^\text{th}$ $1/2^i$

Dlaczego to jest niemożliwe? Czy istnieje dolna granica czasu potrzebnego do przeprowadzenia nietrywialnych obliczeń?

computability computation-models

— dsaxton
źródło

Powiązana koncepcja, nieskończone obliczenia z wykorzystaniem skończonej energii: wieczna inteligencja Dysona .

— Piotra,

Odpowiedzi:

Ten „rodzaj” komputera jest znany jako Maszyna Zeno . Jego model obliczeniowy należy do kategorii o nazwie Hyperkomputacja . Modele hiper obliczeniowe są abstrakcjami matematycznymi, a ze względu na sposób, w jaki są zdefiniowane do pracy, nie są fizycznie możliwe.

Weź na przykład swoją maszynę Zeno. Jeśli wyobrażamy sobie, że Maszyna Zeno jest maszyną obliczeniową dowolnego rodzaju, nie ma znaczenia, czy używa ona liczydła, czy układu scalonego. Powiedz, że dane programu używane przez maszynę są do niego podawane przez nieskończenie długą taśmę symboli (podobnie jak maszyna Turinga).

Oczywiście wiemy z matematyki, że:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n$

który, jak mówimy, jest równy . Zatem obliczenia powinny zakończyć się w ciągu 1 sekundy, ponieważ suma jest absolutnie zbieżna. $1$

Ale ta zbieżność jest oczywiście zależna od dążenia (i osiągania) nieskończoności. W sensie fizycznym oznacza to, że gdy czas wymagany do każdego obliczenia będzie się zmniejszał, „głowica odczytu” maszyny obliczeniowej będzie musiała przesuwać się wzdłuż symboli na taśmie coraz szybciej. W pewnym momencie ta prędkość przekroczy prędkość światła. $n$

Odpowiadając na drugie pytanie, absolutnie najniższa możliwa granica obliczeń prawdopodobnie byłaby rzędu czasu Plancka, biorąc pod uwagę prędkość światła jako główny czynnik ograniczający w teoretycznych, ale fizycznie wiarygodnych modelach obliczeniowych.

— Teoria wszystkiego
źródło

Istnieje również zapotrzebowanie energetyczne dla każdej operacji, przerzucanie nieco razy wymaga kilku rzędów wielkości więcej energii niż jest w naszym słońce

2^{256}

$2^{256}$

— zapadkowy dziwaka

Czy ten program: 10: GOTO 10 kończy się na maszynie Zeno?

— Cano64,

Mówiąc prościej, matematyka zakłada, że „obliczenia” mają nieskończenie podzielny zakres. Jednak nie jest tak w przypadku żadnej fizycznej maszyny, ponieważ w końcu osiągasz punkt, w którym trafiłeś najmniejszą jednostkę pracy, jaką maszyna może wykonać. Po tym punkcie nie można kontynuować dzielenia obliczeń, nawet jeśli matematyka na to pozwala. Innymi słowy, maszyna zawiesza się na długo przed faktycznym zbliżeniem się do końca nieskończonej serii obliczeń. W pewnym momencie czas na obliczenia przestaje maleć, a ty w końcu potrzebujesz nieskończonego czasu.

— aroth

@ Cano64 Nie sądzę. Uważam, że kryterium rozstrzygalności w hiperkomputerach jest to, że suma czasu obliczeń jest absolutnie zbieżna.

— Teoria wszystkiego

Czas potrzebny na prymitywne obliczenia jest ograniczony prędkością światła i rozmiarem atomów, o ile rozumiemy fizykę tego samego dnia, 15 września 2015 r.

Jednostka obliczeniowa musi być zbudowana z czegoś o niezerowym rozmiarze (atomach) i aby obliczenia działały, konieczne będzie przesuwanie się po niej energii elektrycznej lub światła, co będzie ograniczone przez czas, w którym światło przesuwa się po -zero odległości.

— Dave Clarke
źródło

Jednym konkretnym przykładem w najnowszej historii przekraczania granic jest olbrzymia magnetorezystancja , nagrodzone nagrodą Nobla odkrycie, które pozwoliło na gęstość danych na dyskach twardych, które wcześniej uważano za niemożliwe. Jest wiele, wiele więcej, jeśli wrócisz; spróbuj wyjaśnić możliwość „smartfona” osobie od 1500 r. (Mogą cię po prostu spalić jako wiedźmę, więc bądź ostrożny.) Myślę więc, że nie powinniśmy zakładać, że nasza obecna wiedza z fizyki stwarza twarde granice tego, co jest możliwe.

— Raphael

-1

$\Sigma_{n=1}^\infty (\frac{1}{2})^n$ $1$

$\frac{1}{2}$ $\frac{1}{4}$ $\frac{3}{4}$

$c_1$ $c_1$

Edycja : Jak zauważył @aroth, ta analogia zakłada, że możemy dalej dzielić wodę; że nie ma najmniejszego niepodzielnego atomu. Co podnosi interesujący (myślę) punkt, że musimy również założyć, że czas będzie arbitralnie podzielny, aby obliczenia zakończyły się w skończonym czasie.

— epa095
źródło

„i równie wyraźnie, że zawsze będziesz mieć więcej wody w niebieskim wiadrze do przelania” - niekoniecznie. Dzięki wystarczająco precyzyjnemu aparatowi do nalewania w końcu dotrzesz do punktu, w którym w niebieskim wiadrze znajdują się 2 cząsteczki wody. Następnie 1 cząsteczka. Potem albo wlewasz ostatnią cząsteczkę, albo nie. Lub rozbijasz go na podstawowe atomy, ale wtedy nie jest już wodą (lub rozlewa się w STP). Chodzi o to, że dojdziesz do ostatniej cząsteczki wody, zanim dojdziesz do końca nieskończonej serii, więc nie będzie „zawsze” wody w niebieskim wiadrze.

— aroth

@aroth: tak, prawda, aby analogia zadziałała, musisz myśleć o wodzie jako o zadowalającej „gęstości”, rodzaju „zawsze podzielności”. Twój punkt jest interesujący, ponieważ podkreśla coś ważnego; aby obliczenia zakończyły się w skończonym czasie, czas musi być również gęsty / zawsze podzielny. Jeśli istnieje najkrótszy czas, niepodzielna atomowa jednostka czasu, wówczas obliczenia na nieskończoność zajmą nieskończony czas (lub każde obliczenie nie musi zająć czasu po pewnym czasie).

— epa095,

\sum_{i = 1}^{\infty} 2^{- i}

$\sum_{i=1}^\infty 2^{-i}$

2^{- i}

$2^{-i}$

@ david-richerby: Czy przekształcanie problemu w inny sposób nie jest prostsze, ponieważ pozwala łatwiej myśleć o tym, co dokładnie zapewnia intuicja? Należy również pamiętać, że są również przekształcenie problemu, od czasu do sumy liczb wymiernych. (Niezwykle) krótki krok tak, ale podsumowanie. Jeśli wiesz o zbieżności liczb wymiernych, to przekształcenie ułatwia zrozumienie, ale dla niektórych jestem pewien, że łatwiej jest to zrozumieć w kategoriach wody. Przynajmniej tak po raz pierwszy zrozumiałem, dlaczego niektóre nieskończone sumy są zbieżne, a inne nie.

— epa095

@ epa095 Zapewnienie intuicji polega na wyjaśnieniu nieznanej sytuacji poprzez odniesienie do znanej sytuacji i wykorzystanie znajomości jednej sytuacji, aby pomóc zrozumieć drugą. Nie robisz tego: próbujesz wyjaśnić jedną nieznaną sytuację (obliczenie nieskończonej, zbieżnej sumy) inną (nalewanie wiader z nieskończenie podzielnej wody z idealną dokładnością). Ludzie, którzy wiedzą o zbieżności sum, nie potrzebują analogii; dla osób, które nie wiedzą o zbieżności sum, zmiana nazwy „liczba wymierna” na „ilość hipotetycznej wody” nie pomaga.

— David Richerby,