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


15

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 ?



1
Czy obserwator o nieskończonym czasie trwania będzie miał dostęp do nieskończonej energii do wykonywania swoich nieskończonych kroków obliczeniowych? (alternatywnie, czy tester problemów z zatrzymaniem może być sformułowany w sposób odwracalny? Nie sądzę, że tak)
user253751


@immibis: Tak, robi! Studiowałem to na studiach.
Joshua

Zauważ, że powszechne jest błędne przekonanie, że maszyna Turinga, która się nie zatrzymuje, musi „zapętlić się”. To implikuje rodzaj powtarzanego stanu lub robienia tego samego w kółko. W rzeczywistości możemy jednoznacznie stwierdzić, czy maszyna ma takie zachowanie, czy się zatrzymuje, biorąc pod uwagę, że robi to jedno z dwóch. Kłopotliwe maszyny, które nas psują, nie są tymi zapętlonymi, ale raczej tymi, które chaotycznie wirują w niemal losowy sposób, przeciwstawiając się wszelkim zmysłom regularności.
exfret

Odpowiedzi:


26

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.


4
Być może również użyteczne jest to, że formalizm „maszyny hiper-Turinga” jako maszyny Turonga, która może wykonać nieskończoną liczbę kroków w ograniczonym czasie, jest rzeczywiście powszechnym formalizmem. Możesz tam znaleźć wiele przydatnych materiałów.
Cort Ammon - Przywróć Monikę

10

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).


1
Re. „... aby mógł mieć jakikolwiek wpływ na tezę Turinga, musisz istnieć w praktyce”. - czy maszyny Turinga nie są również idealizowanymi maszynami, które nie mogą istnieć w praktyce?
stokrotka

1
W rzeczywistości odzwierciedla on (lub przynajmniej próbuje) naszą intuicję dotyczącą tego, co jest „maszyną obliczeniową”. Dlatego teza Kościoła Turinga jest tezą, a nie twierdzeniem matematycznym. Nieoficjalnie twierdzi, że maszyny Turinga wychwytują prawdziwą moc obliczeniową, która istnieje w naszym świecie.
Ariel,

Chodzi mi o to: dlaczego maszyna Turinga o nieskończonym czasie musi istnieć w praktyce, aby miała jakikolwiek wpływ na CTT, skoro standardowe maszyny Turinga również nie istnieją w praktyce?
stokrotka

1
Jedno sformułowanie tezy Kościoła-Turinga jest następujące: każdy możliwy model obliczeniowy możliwy do zrealizowania w naszym świecie nie przekracza mocy maszyny Turinga. Sama teza jest zdefiniowana w odniesieniu do jakiegoś modelu naziemnego (mianowicie maszyny Turinga).
Ariel,

Zadałem kolejne pytanie, ponieważ nawet po przejrzeniu opublikowanych slajdów nie rozumiem twierdzenia, że ​​nie można zbudować praktycznej kwantowej maszyny Turinga. (Drugi raz, aby opublikować ten komentarz, teraz wskazuje na QC.SE zamiast CS.SE)
BurnsBA 6'18

7

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.


2
„Na razie brakuje wystarczających danych, aby uzyskać sensowną odpowiedź”.
Robert Columbia,

Zauważ, że głównym powodem, dla którego wspomniałem o maszynach Turinga w zamkniętych pętlach czasowych jest to, że istnieją pewne „fizyczne modyfikacje” modelu maszyny Turinga, tak że problem zatrzymania jest obliczalny przez tę maszynę. Wydaje się, że inni wiedzą więcej na temat dylatacji czasu niż ja, ale ten przykład przynajmniej waha się czynić takie twierdzenia, chyba że podano formalizację dylatacji czasu.
Dyskretna jaszczurka

@Discretelizard To był świetny wkład w dyskusję. Nie jestem pewien, czy w pełni rozumiem intencje OP, ale relatywistyczna dylatacja czasu jest prawdziwą koncepcją we współczesnej fizyce, i odpowiedziałam przy założeniu, że używał standardowej definicji tego terminu.
Davislor,

@Davislor Oczywiście dylatacja czasu jest dobrze zdefiniowana w fizyce . Maszyna Turinga jest obiektem matematycznym . O ile mi wiadomo, najlepsze, co możemy zrobić, aby połączyć te dwa elementy, to stworzyć „fizyczną analogię” maszyny Turinga i formalnie pokazać, jak to współdziała z dylatacją czasu. To jest (przykład), co mam na myśli przez „formalizację”. Nie sądzę, aby istniał wyjątkowy sposób sformalizowania tego i że wyniki mogą się różnić, dlatego waham się, aby powiedzieć coś rozstrzygającego na ten temat.
Dyskretna jaszczurka

Powiedział, że to mogło być możliwe, że odpowiedź brzmi „nie” dla każdego rozsądnego formalistation, ale takie roszczenie jest poza moim doświadczeniem, co najmniej.
Dyskretna jaszczurka

5

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 ( 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.


1

Cytat z Bangs, Crunches, Whimpers i Scieks:

π
(x1)(x2))(xn)fa(xl,x2),,xn)γ1nγ1czerpie 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.
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.