Co jest wymagane do uniwersalnego obliczenia analogowego?

Jakie operacje należy wykonać, aby wykonać dowolne obliczenia analogowe ? Czy dodawanie, odejmowanie, mnożenie i dzielenie byłoby wystarczające?

Ponadto, czy ktoś dokładnie wie, jakie problemy można rozwiązać za pomocą obliczeń analogowych, ale nie w przypadku cyfrowej?

Niestety nie ma „uniwersalnej” koncepcji uniwersalności w obliczeniach analogowych. Jednak ten artykuł Delvenne'a proponuje jednoczący formalizm uniwersalności w dyskretnych (np. Maszynach Turinga) i ciągłych (np. Równaniach różniczkowych) układach dynamicznych oraz dokonuje przeglądu niektórych uniwersalnych układów badanych w literaturze. Oto fragment artykułu, który nieformalnie opisuje procedurę dowodzenia uniwersalności układu dynamicznego:

Jednak większość układów dynamicznych badanych w matematyce i fizyce ma niezliczoną przestrzeń stanów, np. Automaty komórkowe, równania różniczkowe, fragmentaryczne mapy liniowe itp. Przykłady tych układów okazały się uniwersalne. Problem zatrzymania jest imitowany z maszyny Turinga w następujący sposób. Wybieramy konkretną policzalną rodzinę stanów początkowych i policzalną rodzinę stanów końcowych lub ostatecznych zbiorów stanów. Następnie problem zatrzymania otrzymuje stan początkowy i stan końcowy / zestaw stanów, czy trajektoria rozpoczynająca się od stanu początkowego osiągnie stan końcowy / zestaw stanów. Bardziej szczegółowe przykłady podano w sekcji 7.

Jean-Charles Delvenne, Co to jest uniwersalna maszyna komputerowa ?, Matematyka Stosowana i Obliczenia, Tom 215, Wydanie 4, 15 października 2009, Strony 1368-1374

Nie sądzę, aby na pytanie można było odpowiedzieć, chyba że mamy definicję tego, o jakich obliczeniach mówimy.

Uniwersalność modelu maszyny w klasie obliczeniowej oznacza, że ​​każde obliczenie w tej klasie może być obliczone przez maszynę. O ile nie zdefiniujesz klasy „arbitralnych obliczeń analogowych”, nie będziemy w stanie odpowiedzieć na to, co im się powiedzie.

Teraz wymienione funkcje dadzą ci tylko wielomiany i ich iloraz, który jest raczej małą klasą funkcji rzeczywistych, nie możesz nawet obliczyć prostych funkcji, takich jak , ⌊ x ⌋ , $2^x$$\lfloor x \rfloor$ , ... używając ich.$\sqrt x$

Jeśli twoim pytaniem jest, czy istnieją systemy fizyczne, które zaczynając od stanu początkowego osiągną inny stan za jakiś czas i jeśli zawsze jest to możliwe do obliczenia, odpowiedź zależy od tego, o jakiej fizyce mówimy i co to znaczy skonfigurować wstępna konfiguracja i obserwacja wyniku itp.

Jeśli mówimy tylko matematycznie o fizyce klasycznej (możemy ustawić dowolną konfigurację początkową na nieskończoną precyzję i bez żadnych rozważań na temat rzeczy takich jak energia potrzebna do skonfigurowania konfiguracji i obserwowania wyniku jest podobnie z matematycznego punktu widzenia), to było to wiadome przez długi czas istniały równania różniczkowe dotyczące funkcji obliczeniowych, ponieważ ich rozwiązanie nie jest obliczalne, patrz Marian B. Pour-El i J. Ian Richards, „ Computability in Analysis and Physics ”, 1989.

Ciekawym przypadkiem jest to, że problem n-ciała jest obliczalny (i jeśli dobrze pamiętam, odpowiedź brzmi nie, przynajmniej dla $n>4$ ).

Zasadniczo, jeśli możemy po prostu sprawdzić równość dwóch liczb rzeczywistych, co daje funkcję, która nie jest ciągła, wpisujemy typowe typologie informacji o liczbach rzeczywistych, a zatem nie mogą być obliczone przez maszynę Turinga, ponieważ jakakolwiek funkcja (w tym funkcje wyższego typu) niż maszyna Turinga Potrafi obliczyć jest ciągły (wrt topologii informacji).

TL; DR: Jeśli przez „komputery analogowe” rozumiesz analizatory różnicowe , odpowiedzią są sumatory, jednostki stałe i integrator. Bournez, Campagnolo, Graça i Hainry wykazali w 2006 r. ( Płatny / darmowy przedruk ), że jego wyidealizowany model umożliwia obliczenie wszystkich funkcji obliczeniowych w ramach analizy obliczeniowej , a model ten potrzebuje tylko tych 3 rodzajów jednostek.

Funkcje transcendentalne

$\sin$$\exp$$\log$

Analogowe modele obliczeniowe

Jak podkreślają inni, koncepcja „obliczeń uniwersalnych” jest mniej jasna dla komputerów analogowych niż dla komputerów standardowych, gdzie inne naturalne pojęcie obliczalności w różnych modelach obliczeniowych znalazło równoważne w latach 30. XX wieku (szczegóły na stronie Wikipedii na temat tezy Churcha Turinga ) .

Aby zdefiniować taką uniwersalność, należy najpierw zdefiniować dobry model obliczeń analogowych i jest to trudne zadanie, ponieważ model powinien być idealizowany i wystarczająco naturalny, aby był użyteczny, ale jego idealizacja nie powinna dawać nierealistycznej mocy Model. Przykładem takiej dobrej idealizacji jest nieskończona taśma maszyn Turinga. Problem z komputerami analogowymi wiąże się z liczbami rzeczywistymi, które mogą pozwolić na zbudowanie nieracjonalnych rzeczy, takich jak maszyna Zeno . Jednak kilka takich modeli zostało zaproponowanych i wykorzystanych w literaturze (GPAC jest głównym tematem tej odpowiedzi, ale staram się być kompletny na poniższej liście, bez żadnego hiperkomputera ):

• General Purpose Analog Computer (GPAC), zdefiniowane przez Claude E.Shannon w 1941 ( paywalled pdf ) do modelowania analizatory różniczkowe . Definicja GPAC została ostatnio dopracowana, a jej moc obliczeniowa skorygowana w górę;
• maszyna Blum-Shub-Smale , która działa w dyskretnych czasach na liczbach rzeczywistych. Jest ściśle związany z modelem rzeczywistej pamięci RAM często stosowanym w geometrii obliczeniowej;
• $\mathbb R$
• Sieci neuronowe ;
• Analiza obliczeniowa , która analizuje liczby rzeczywiste obliczalne przez maszynę Turinga.

Moc modelu GPAC

$\Gamma$$\zeta$$y(t)=\Gamma(t)$Przez długi czas wydawało się, że taki komputer analogowy nie jest „uniwersalny”, ponieważ nie jest w stanie wygenerować rozsądnych funkcji obliczeniowych, z których korzystają matematycy.

$f$$y(t)$$f(x)$$x$$\gamma$$\zeta$.

Bournez, Graça i Pouly wykazali następnie w 2013 r., Że te komputery analogowe mogą skutecznie symulować maszynę Turinga (s. 181 dużego pliku pdf ), aw 2014 r., Że klasy złożoności P i NP są równoważne w tym modelu.

Czy użyteczne byłoby zaproponowanie, aby uniwersalny system analogowy mógł być modelowany przez nieskończoną sieć neuronową, tj. Dowolne inne wartości wejściowe / wyjściowe systemu analogowego mogą być replikowane dla dopasowanej sieci neuronowej dla danej operacji, a operacje mogą być łączone w zależności od potrzeb?

Chociaż sam sformułowałem tę myśl, kolejne wyszukiwanie wykazało podobną propozycję:

Wyłania się teza podobna do Churcha-Turinga, zastosowana w dziedzinie obliczeń analogowych, która przedstawia model sieci neuronowej zamiast cyfrowej maszyny Turinga (patrz tutaj ).

Prawdopodobnie wszystko, czego potrzebujesz, to prymitywne operacje, aby przenieść wartość z jednego węzła do drugiego. Bez mankietu, który może być plusem, minusem i podzielić, aby uzyskać stosunek między połączeniami.

Teraz, jeśli chodzi o nierozwiązywalne problemy, spójrz, gdzie sieci neuronowe zostały z powodzeniem zastosowane lub są słabe, ponieważ zostały wdrożone na dyskretnym komputerze.

(i przepraszam, jeśli mój prawie świecki pogląd na ten temat jest rażąco oczywisty)