Maszyna Turinga + dylatacja czasu = rozwiązać problem zatrzymania?

Istnieją relatywistyczne czasoprzestrzenie (np. Czasoprzestrzenie MH; patrz Hogarth 1994), w których linia świata o nieskończonym czasie trwania może być zawarta w przeszłości skończonego obserwatora. Oznacza to, że normalny obserwator może mieć dostęp do nieskończonej liczby kroków obliczeniowych.

Zakładając, że komputer może funkcjonować idealnie przez nieskończony czas (i wiem, że to duże pytanie): można zbudować komputer HM, który podróżuje wzdłuż tej nieskończonej linii świata, obliczając problem zatrzymania dla danego M. Jeśli M zatrzyma się , HM wysyła sygnał do skończonego obserwatora. Jeśli po nieskończonej liczbie kroków obserwator nie otrzyma sygnału, obserwator wie, że M zapętla się, rozwiązując problem zatrzymania.

Jak dotąd wydaje mi się to w porządku. Moje pytanie brzmi: jeśli to, co do tej pory powiedziałem, jest poprawne, w jaki sposób zmienia to dowód Turinga, że ​​problem zatrzymania jest nierozstrzygalny? Dlaczego jego dowód zawodzi w tych czasoprzestrzeni ?

Zauważ, że dowód Turinga dotyczy matematyki, a nie fizyki. W ramach zdefiniowanego modelu maszyny Turinga udowodniono nierozstrzygalność problemu zatrzymania i jest to fakt matematyczny. Dlatego dowód Turinga nie „zawiedzie” się w czasoprzestrzeni, po prostu nie udowodni nic na temat związku problemu zatrzymania i dylatacji czasu.

Jednak prawdopodobnie będziesz chciał wiedzieć, czy „maszyna Turinga do rozszerzania czasu” może rozwiązać problem zatrzymania.

Jeśli chcesz przestudiować wpływ „dylatacji czasu” na maszynę Turinga, musisz określić formalny model, dzięki któremu możemy formalnie zrozumieć, co to znaczy dla maszyny Turinga wykorzystanie dylatacji czasu. Niestety ten format jest nieodpowiedni do zapewnienia takiego formalnego modelu (chyba że ktoś napisał o nim artykuł), ponieważ tworzenie modelu jest zdecydowanie zbyt szerokie.

Jednak nie jest mało prawdopodobne, aby jakaś formalizacja rzeczywiście była w stanie rozwiązać problem zatrzymania. W tym artykule Scott Aaronson, Mohammad Bavarian i Giulio Gueltrini przyglądają się modelom obliczeniowym przy założeniu, że istnieją tak zwane Pętle podobne do czasu zamkniętego i stwierdzają, że problem zatrzymania jest rzeczywiście obliczalny w ramach tego modelu.

Maszyna Turinga jest formalnym matematycznym modelem obliczeń, nie odpowiada na żadne ograniczenia fizyczne i nie dba o efekty relatywistyczne. Oznacza to, że dowód Turinga nie zawodzi, ponieważ standardowa definicja maszyny Turinga nie zawiera nawet pojęcia „czasoprzestrzeni”.

Możesz spróbować zdefiniować inny model obliczeń inspirowany względnością. Znowu będzie to tylko obiekt formalny, a pytanie, czy może rozwiązać problem zatrzymania, należy do dziedziny matematyki i zależy od konkretnej definicji. Jednak prawdziwe pytanie brzmi teraz: czy ten nowy model rzeczywiście poprawnie rejestruje efekty relatywistyczne, tj. Czy naprawdę odzwierciedla naszą fizykę i może zostać zaimplementowany w naszym świecie?

Możesz zobaczyć taką dyskusję dotyczącą obliczeń kwantowych. Mamy formalną definicję „kwantowych maszyn Turinga”, a ich dokładna moc obliczeniowa pozostaje otwartym problemem w matematyce (choć nawet nie jest bliska problemu zatrzymania). Mimo to możesz argumentować, że ta definicja tak naprawdę nie odzwierciedla naszego zrozumienia fizyki kwantowej i potrzebna jest lepsza. Istnieją argumenty sugerujące, że takich maszyn nie można nawet zbudować, więc ich dokładna moc nie ma wpływu na (mocną) tezę Turinga.

Wróć do twojego pytania. Istnieje formalne pojęcie maszyny Turinga o nieskończonym czasie , ale aby mogła ona mieć jakikolwiek wpływ na tezę Kościoła-Turinga, musi ona istnieć w praktyce. Być może zainteresuje Cię artykuł Scotta , który zawiera rozdział o obliczeniach wykorzystujących efekty relatywistyczne, choć wydaje się, że naiwne argumenty są beznadziejne (w tym sensie, że są niepraktyczne, ponieważ koszt czasu zastępuje się kosztem energii).

Dowód Turinga pokazuje, że żadna maszyna Turinga nie rozwiąże problemu zatrzymania, bez względu na to, ile czasu mu dasz. Jeśli twój statek kosmiczny wykorzystał dylatację czasu, aby dać komputerowi miliard lat pracy, nadal może nie być w stanie powiedzieć ci nic bardziej określonego niż „jeszcze nie”.

Najwyraźniej (Dzięki, @DiscreteLizard!), Jeśli masz podróż w czasie, która nie może powodować paradoksów, możesz ustawić pętlę czasu , która spowodowałaby paradoks, gdyby komputer nie mógł udowodnić, czy maszyna Turinga się zatrzyma. Albo otrzymuje odpowiedź z przyszłości i przesyła ją z powrotem do siebie, albo działa wiecznie (i sprytnie zwraca kwantową superpozycję, która ustala się w stabilnej pętli czasowej). Ale zanim spróbujesz tego, bądź bardzo pewny, że bezpiecznie jest wywołać paradoks podróży w czasie.

Zarzut polega na tym, że zdefiniowałeś proces, który może tworzyć nieskończoną entropię w zwartym regionie i który wydaje się to robić w skończonym segmencie przeszłości obserwatora. To oznacza kilka rzeczy

• Entropia obliczeniowa w zwartym regionie przekracza Bekensteinzwiązana na entropii (która jest proporcjonalna do powierzchni regionu), więc zapada się w czarną dziurę (natychmiast) i żaden sygnał nie może do ciebie dotrzeć z jej wnętrza. (Metryka Kerr opisuje czasoprzestrzeń MH. Obserwuje się nieskończony proces, gdy obserwator przechodzi do wewnętrznego horyzontu zdarzeń. Pomijając obecną niepewność dotyczącą fizyki takiego przejścia, żaden zdalny obserwator nigdy nie ma dostępu do wyniku obliczeń - wynik ma tylko obserwator, który zniknął w czarnej dziurze. Nie jest to opis przydatnego procesu obliczeniowego. Parafrazując: „Mamy wyrocznię, która daje prawidłową odpowiedź na każde pytanie, które zadajesz w sposób ciągły w takim czasie. sposób, w jaki odpowiedź istnieje tylko w chwili, gdy zostanie zniszczona przez spłukanie jej czarnej dziury. ”)
• Maszyna Turinga niszczy informacje za każdym razem, gdy nadpisuje symbol na taśmie, dlatego zgodnie z zasadą Landauera należy obserwować skończone obliczenia na linii nieskończonego świata skompresowanego do skończonego segmentu w przeszłości stożek światła obserwacji, aby wymagać nieskończonej mocy i emitować nieskończone ciepło podczas nieskończenie małego czasu, w którym obserwuje się jego działanie. Oznacza to, że ponieważ zatrzymanie jest osiągane w skończonym czasie, jest ono osiągane natychmiastowo z punktu widzenia zewnętrznego obserwatora, więc cała moc jest zużywana natychmiast, a całe ciepło natychmiast ewoluuje. Alternatywnie, jeśli obliczenia się nie zatrzymają, zwarty obszar stale zużywa nieskończoną moc i emituje nieskończone ciepło. Wynik netto: znowu czarna dziura.
• Alternatywnie, zasada Landauer nie stosuje się do odwracalnego informatyki i tam są ( uniwersalne ) pługi maszyny Turinga . Jednak taka maszyna Turinga wymaga zdolności do przedstawienia całej przestrzeni potencjalnych stanów obliczeniowych, która jest wykładnicza pod względem wielkości użytej taśmy, więc szybko wpada do granicy Bekensteina. Ostatecznie jesteśmy w stanie uniknąć problemu cieplnego tylko poprzez ograniczenie do taśm o ograniczonej długości. Równolegle mamy górną granicę użytecznej długości taśmy kontrolowaną przez powierzchnię regionu, który ma nieskończoną linię świata. Jeśli nie uwzględnisz tego, a twoje obliczenia zużyją za dużo taśmy, znowu pojawi się czarna dziura.

Ciekawe, otwarte pytanie, czy i jak ograniczenia te dotyczą komputerów kwantowych. Może się zdarzyć, że złożoność obliczeń wykonywanych przez komputer kwantowy jest ograniczona przez powierzchnię komputera. Być może będziemy musieli podwoić powierzchnię ekstremalnego komputera kwantowego, aby uzyskać jeszcze jeden użyteczny kubit obliczeń. To szybko prowadzi do niepraktycznie dużych komputerów.

Cytat z Bangs, Crunches, Whimpers i Scieks:

$\pi$

$(\exists x_1)(\exists x_2)\dots(\exists x_n)F(x_l,x_2,\dots,x_n)$$\gamma_1$$n$$\gamma_1$czerpie z tych prac wiedzę na temat prawdziwej wartości tego twierdzenia. Ale gdy tylko w grę wchodzą mieszane kwantyfikatory, metoda zawodzi. Jednak Hogarth (1994) wykazał, jak bardziej skomplikowane układy w ogólnych relatywistycznych czasoprzestrzeniach można w zasadzie wykorzystać do sprawdzenia prawdziwości wartości arytmetycznego twierdzenia o dowolnej złożoności ilościowej. W takiej czasoprzestrzeni trudno jest zrozumieć, jak utrzymać postawę, że nie mamy jasnego pojęcia prawdy w arytmetyce.