W jaki sposób modele hiper obliczeń pokonują problem zatrzymania?

Hyperkomputer odnosi się do modeli obliczeniowych, których nie można symulować za pomocą maszyn Turinga. (Hyperkomputery niekoniecznie są fizycznie możliwe do zrealizowania!) Niektóre hiperkomputery mają dostęp do zasobu, który pozwala na rozwiązanie problemu zatrzymania dla standardowych maszyn Turinga. Nazwij to „supermocarstwem”: hiperkomputer z supermocarstwem może zdecydować, czy zakończy się jakakolwiek standardowa maszyna Turinga.

Jakiego rodzaju „supermoce” wykorzystują hiperkomputery?

Teza Eda Blakey'a ustanawia formalne ramy do klasyfikowania niektórych głównych rodzajów zasobów wykorzystywanych w hiperkomputerach, ale nie stara się zapewnić kompleksowej analizy supermocarstw. Nie interesuje mnie lista hiperkomputerów (ładna lista w artykule na Wikipedii), ale zrozumienie, jakiego „specjalnego sosu” używa każdy model, być może uważanego za unikalny rodzaj zasobu.

To pytanie jest inspirowane tym, jak fundamentalna jest nierozstrzygalność? . Powiązane jest również pytanie: Co to znaczy obalić tezę Turinga? który wygenerował wiele interesujących dyskusji, i czy są obecnie badane jakieś modele obliczeń z możliwością większej mocy niż maszyny Turinga? .

W artykule O sile mnożenia w maszynach o swobodnym dostępie Hartmanis udowodnił, że jeśli dodamy instrukcję mnożenia kosztu jednostkowego w pamięci RAM (zwanej MRAM), to dla tego modelu P = NP. Ponadto językami ustalonymi w czasie wielomianowym w modelu MRAM są dokładnie te języki w PSPACE.

Jak stwierdzono w artykule, wyniki te pokazują, że mnożenie ma taką samą złożoność jak dodawanie iff P = PSPACE.

Bardziej powiązany wynik, o którym słyszałem, jest taki, że jeśli dodamy instrukcję RAM z nieskończoną precyzją w pamięci RAM, możemy rozwiązać nierozstrzygalne problemy. Nie mogłem jednak znaleźć papieru potwierdzającego ten wynik. Jeśli ktoś to zna, proszę o komentarz, a ja zaktualizuję odpowiedź.

Odkryłeś więc, że bazy danych nie mogą rozwiązać każdego problemu! Pierwszym krokiem, jaki zrobił Turing i jest wysoce logiczne (choć nie jest to trywialne, jeśli weźmie się pod uwagę stan obliczeń w tym czasie), było wyrocznie.

Nieoficjalnie dodajesz do swojej maszyny nowy moduł czarnej skrzynki, który może „jakoś” rozwiązać problem, którego twój komputer nie może, powiedzmy, problem zatrzymania. Oczywiście wyrocznie są tylko matematyczną abstrakcją i nie kryje się za ich wewnętrznym działaniem. Osobiście nie widzę sposobu, w jaki wyrocznia mogłaby zostać wykorzystana do odkrycia modelu, który obaliłby tezę Turinga.

• Manipulowanie czasem i przestrzenią

Ponieważ problemem związanym z rozwiązaniem problemu zatrzymania jest wiedza, kiedy maszyna się zatrzyma, uruchomienie maszyny w czasoprzestrzeni innej niż nasza może pozwolić na jej rozwiązanie. Z moich źródeł, kiedy pisałem raport na temat modeli, które można skutecznie rozwiązać$NP$, fizycy teoretyczni uważają, że warunki te są spełnione w pobliżu krawędzi czarnych dziur. Aby to zrobić, musisz mieć maszynę komputerową bardzo blisko czarnej dziury, ale nie w jej horyzoncie zdarzeń (aby się nie wciągnęła). Następnie nurkujesz w czarnej dziurze i możesz przeglądać całą nieskończoną oś czasu swojej maszyny w skończonym czasie. Prawdopodobnie oznacza to, że wciągnięto cię do czarnej dziury, więc sądzę, że nie zostanie ona wdrożona i przetestowana, nawet gdybyśmy mogli dotrzeć do czarnej dziury. To wszystko jest nieformalne, zaczynasz czytać bardziej teoretyczne podejście do fizyki z artykułu w Wikipedii na temat Malament-Hogarth_spacetime . Pomocnym cytatem jest także artykuł. Czy ogólna teoria względności pozwala obserwatorowi spojrzeć na wieczność w skończonym czasie?

• Maszyna Zeno może rozwiązać każdy problem w ciągu 2 sekund, ale jest to matematyczna hipotetyczna konstrukcja, w której każdy krok zajmuje o połowę mniej czasu, a pierwszy raz zajmuje 1 sekundę. Nie zapewnia rzeczywistego rozwiązania, które można wdrożyć.

Są inne modele, o których wiem, ale myślę, że po prostu rozwijają pomysły, które tu przedstawiłem, lub są czysto matematycznymi konstrukcjami, więc bardziej przypominają „zgrabne sztuczki” niż coś, co mogłoby obalić tezę Turinga.

Nie do końca to, o co prosiłeś, ale Scott Aaronson ma artykuł, dobrze wyjaśniony tutaj na temat maszyn Turinga z możliwością podróżowania w czasie, ale z wymogami samozachowawczości (tzn. Nie możesz wrócić do przeszłości, aby zmienić przeszłość. Możesz obserwować przyszłość , ale musi być zgodny z teraźniejszością).