Czy nierozwiązywalność problemu N-ciała jest równoważna problemowi zatrzymania

16

Nie ma ogólnego analitycznego rozwiązania problemu n-ciała, który mógłby wytworzyć funkcję analityczną, która mogłaby zostać użyta do nadania stanu układu n-ciała w dowolnej chwili t z dokładną dokładnością. Istnieją jednak pewne szczególne przypadki układów n-ciała, dla których znana jest funkcja analityczna.

W podobny sposób nie ma ogólnego algorytmu, który mógłby przewidzieć wynik działania dowolnej maszyny Turinga. Chociaż istnieje wiele rodzajów tokarek, które można ustalić, aby zatrzymać lub uruchomić na zawsze.

Czy te dwa wyniki są równoważne? Czy dowód jednego z nich implikuje drugi? Czy magiczna maszyna, która jest w stanie rozwiązać problem zatrzymania, byłaby w stanie dokładnie przewidzieć stan układu n-ciała? Lub odwrotnie, czy ogólne analityczne rozwiązanie problemu n-ciała pozwoliłoby nam zdecydować o problemie zatrzymania na dowolnej maszynie Turinga?

Moje początkowe przypuszczenie, jak do tego podejść, byłoby wykazanie, że układ grawitacyjny n-ciała jest kompletny w Turingu. Podejrzewam, że uważa wszechświat za kompletny Turinga i zasadniczo działa pod wpływem grawitacji (i kilku innych sił, które zachowują się podobnie), ale nie mam pojęcia, jak to udowodnić.

Ale jestem sceptyczny, że takie podejście jest wystarczające, biorąc pod uwagę, że uważam za możliwe (choć uważam to za mało prawdopodobne), że brak ogólnego analitycznego rozwiązania problemu n-ciała może być niezależny od tego, czy Turing jest kompletny.

Edycja: Po przeczytaniu kilku innych powiązanych ze sobą pytań, zdałem sobie sprawę, że liczba wymiarów, w których działa grawitacja, może być istotna dla pytania. Pytam konkretnie o grawitację w 3 wymiarach przestrzennych. Ale, biorąc pod uwagę fakty takie, jak trzeba co najmniej 3 zasady, aby uniwersalną maszynę Turinga i wagę w 2 wymiarach miałaby tylko prawo odwrotną zamiast prawa odwrotnych kwadratów , w wyniku nie zamknięte orbity , widzę, że grawitacja w trzech wymiarach jest Turinga kompletna, ale nie w dwóch lub jednym.∝1/r∝1/r2)

computability turing-machines undecidability computation-models Shufflepants
źródło
1
Twoim zadaniem jest zadać sobie pytanie, ale obawiam się, że możesz używać technicznych słów i pojęć, nie dbając o to, czy mogą mieć znaczenie w kontekście, w którym zdecydujesz się ich użyć. To nie jest zbyt naukowe. Nie twierdzę, że spekulowanie jest niewłaściwe, ale wymaga pewnej ostrożności. Co to może znaczyć, że problem n-ciała jest ukończony przez Turinga? Co może być wyliczeniem Gödela problemów n-ciała? Nawiasem mówiąc, Turing zawsze pisze wielką literą T., jesteśmy mu przynajmniej winni.
babou
Mam na myśli to, że problem n-ciała jest ukończony w Turingu w tym samym sensie, co gra życia Conwaya w Turingu ukończona; że możesz ustawić układ cząstek punktowych grawitacji i wykorzystać ewolucję stanu tego układu do wykonania obliczeń.
Shufflepants
Nie wiem, co wszystko można zakodować w położeniu, prędkości lub przyspieszeniu szeregu cząstek punktowych o różnych lub identycznych masach. Pytam wprost, czy istnieje takie kodowanie, ponieważ nie wiem.
Shufflepants
1
Gra życia Conwaya jest teorią automatu komórkowego, bardzo dyskretną strukturą, jak maszyny Turinga. Możemy więc sobie wyobrazić, że można zakodować jedno w drugie. Ale problem n-ciała występuje w świecie równań różniczkowych, funkcji ciągłych i tym podobnych ... Nie jestem pewien, czy zakodować jedno w drugie. Możecie mieć nadzieję (choć wątpię, a i tak jestem niekompetentny), że nieistnienie analitycznego rozwiązania problemu n-ciała byłoby konsekwencją sprzeczności wewnętrznej każdej teorii wyrażającej ten problem, trochę jak dowód problemu zatrzymania.
babou
1
Twoja najlepsza szansa to problem matematyczny. Fizycy powiedzą ci, że n-ciało jest chaotyczne, wrażliwe na motyla, tak że fluktuacje kwantowe zabijają wszelkie kodowanie dalekiego zasięgu lub jakąkolwiek przewidywalność ewolucji systemu, co nie działa zbyt dobrze dla maszyny Turinga. Ludzie matematyki mogą powiedzieć coś gorszego, ale na szczęście nie wiem, co to jest.
babou

Odpowiedzi:

9

n2)

Zobacz np

vzn
źródło
Nie miałem okazji w pełni przeczytać i zrozumieć tego pierwszego artykułu, ale wygląda na to, że prawdopodobnie tak blisko jest odpowiedzieć na moje pytania, jak można się spodziewać. Tak więc akceptuję tę odpowiedź.
Shufflepants