Hiperobliczanie - Hypercomputation

Obliczenia hiperobliczeniowe lub super-Turing odnoszą się do modeli obliczeń, które mogą zapewnić dane wyjściowe, które nie są obliczalne według Turinga . Na przykład maszyną, która mogłaby rozwiązać problem z zatrzymaniem, byłby hiperkomputer; tak też byłby taki, który może poprawnie ocenić każde stwierdzenie w arytmetyce Peano .

The Church-Turinga teza stwierdza, że każda funkcja „obliczalny”, które mogą być obliczane przez matematyka z pióra i papieru przy użyciu skończony zestaw prostych algorytmów, można obliczyć przez maszynę Turinga. Hiperkomputery obliczają funkcje, których maszyna Turinga nie może i które w związku z tym nie są obliczalne w sensie Churcha-Turinga.

Technicznie rzecz biorąc, wynik losowej maszyny Turinga jest nieobliczalny; jednak większość literatury dotyczącej hiperkomputerów koncentruje się zamiast tego na obliczaniu deterministycznych, a nie losowych, nieobliczalnych funkcji.

Historia

Model obliczeniowy wykraczający poza maszyny Turinga został wprowadzony przez Alana Turinga w jego rozprawie doktorskiej z 1938 r. Systemy logiki oparte na liczbach porządkowych . W tym artykule zbadano systemy matematyczne, w których dostępna była wyrocznia , która może obliczyć pojedynczą arbitralną (nierekurencyjną) funkcję od naturalnych do naturalnych. Użył tego urządzenia, aby udowodnić, że nawet w tych mocniejszych systemach wciąż występuje nierozstrzygalność . Maszyny wyroczni Turinga są matematycznymi abstrakcjami i nie są fizycznie możliwe do zrealizowania.

Przestrzeń stanów

W pewnym sensie większość funkcji jest nieobliczalna: istnieją funkcje obliczalne, ale istnieje niepoliczalna liczba ( ) możliwych funkcji Super-Turinga.

Modele

Modele hiperkomputerów wahają się od użytecznych, ale prawdopodobnie niemożliwych do zrealizowania (takich jak oryginalne maszyny wyroczni Turinga), do mniej użytecznych generatorów funkcji losowych, które są bardziej „realizowalne” (takie jak losowa maszyna Turinga ).

Nieobliczalne wejścia lub komponenty czarnej skrzynki

System dawał wiedzę o nieobliczalnej, wyroczni stałej Chaitina (liczba z nieskończoną sekwencją cyfr, która koduje rozwiązanie problemu zatrzymania) jako dane wejściowe, które mogą rozwiązać dużą liczbę użytecznych, nierozstrzygalnych problemów; system, któremu przyznano nieobliczalny generator liczb losowych jako dane wejściowe, może tworzyć losowe, nieobliczalne funkcje, ale ogólnie uważa się, że nie jest w stanie sensownie rozwiązać „użytecznych” nieobliczalnych funkcji, takich jak problem zatrzymania. Istnieje nieograniczona liczba różnych typów hiperkomputerów, które można sobie wyobrazić, w tym:

  • Oryginalne maszyny wyroczni Turinga, zdefiniowane przez Turinga w 1939 roku.
  • Prawdziwy komputer (rodzaj wyidealizowanych komputer analogowy ) może wykonywać hiperkomputer jeśli fizyka przyznaje ogólne realne zmienne (nie tylko obliczalne Real ), a te są w jakiś sposób „harnessable” za przydatne (zamiast losowego) obliczeń. Może to wymagać dość dziwacznych praw fizyki (na przykład mierzalnej stałej fizycznej o wartości wyroczni, takiej jak stała Chaitina ) i wymagać zdolności do pomiaru rzeczywistej wartości fizycznej z dowolną precyzją, chociaż standardowa fizyka czyni taką arbitralną -precyzyjne pomiary teoretycznie niewykonalne.
    • Podobnie sieć neuronowa, która w jakiś sposób miałaby stałą Chaitina dokładnie wbudowaną w jej funkcję wagową, byłaby w stanie rozwiązać problem zatrzymania, ale jest podatna na te same trudności fizyczne, co inne modele hiperobliczeń oparte na obliczeniach rzeczywistych.
  • Pewne „rozmyte maszyny Turinga” oparte na logice rozmytej mogą z definicji przypadkowo rozwiązać problem zatrzymania, ale tylko dlatego, że ich zdolność do rozwiązania problemu zatrzymania jest pośrednio założona w specyfikacji maszyny; jest to postrzegane jako „błąd” w oryginalnej specyfikacji maszyn.
    • Podobnie, proponowany model znany jako sprawiedliwy niedeterminizm może przypadkowo pozwolić na prorocze obliczenia funkcji nieobliczalnych, ponieważ niektóre takie systemy z definicji mają wyroczną zdolność do identyfikowania odrzuconych danych wejściowych, które „niesprawiedliwie” spowodowałyby, że podsystem będzie działał w nieskończoność.
  • Dmytro Taranovsky zaproponował finitystyczny model tradycyjnie niefinitystycznych gałęzi analizy, zbudowany wokół maszyny Turinga wyposażonej w szybko rosnącą funkcję jako jej wyrocznia. Dzięki temu i bardziej skomplikowanym modelom był w stanie podać interpretację arytmetyki drugiego rzędu. Modele te wymagają nieobliczalnych danych wejściowych, takich jak fizyczny proces generowania zdarzeń, w którym odstęp między zdarzeniami rośnie w nieobliczalnie dużym tempie.
    • Podobnie, jedna nieortodoksyjna interpretacja modelu nieograniczonego niedeterminizmu zakłada, z definicji, że czas potrzebny na rozliczenie się „aktora” jest zasadniczo niepoznawalny, a zatem nie można udowodnić w ramach modelu, że nie zajmuje nieobliczalnie długi okres czasu.

Modele „nieskończonych kroków obliczeniowych”

Aby działać poprawnie, niektóre obliczenia przez maszyny poniżej dosłownie wymagają nieskończonej, a nie tylko nieograniczonej, ale skończonej, fizycznej przestrzeni i zasobów; w przeciwieństwie do maszyny Turinga, każde obliczenie, które się zatrzymuje, będzie wymagało tylko skończonej fizycznej przestrzeni i zasobów.

  • Maszyna Turinga, która może wykonać nieskończenie wiele kroków w skończonym czasie, wyczyn znany jako superzadanie . Sama możliwość uruchomienia nieograniczonej liczby kroków nie wystarczy. Jednym z modeli matematycznych jest maszyna Zeno (zainspirowana paradoksem Zenona ). Maszyna Zeno wykonuje swój pierwszy krok obliczeniowy za (powiedzmy) 1 minutę, drugi krok za ½ minuty, trzeci krok za ¼ minuty itd. Sumując 1+½+¼+... ( seria geometryczna ) widzimy, że maszyna wykonuje nieskończenie wiele kroków w sumie 2 minuty. Według Shagrira, maszyny Zeno wprowadzają fizyczne paradoksy, a ich stan jest logicznie nieokreślony poza okresem jednostronnie otwartym [0, 2), a więc nieokreślony dokładnie 2 minuty po rozpoczęciu obliczeń.
  • Wydaje się naturalne, że możliwość podróżowania w czasie (istnienie zamkniętych krzywych czasopodobnych (CTC)) sama w sobie umożliwia hiperobliczanie. Jednak tak nie jest, ponieważ CTC nie zapewnia (sam w sobie) nieograniczonej ilości pamięci, której wymagałyby nieskończone obliczenia. Niemniej jednak istnieją czasoprzestrzenie, w których region CTC można wykorzystać do relatywistycznych hiperobliczeń. Według artykułu z 1992 roku, komputer działający w czasoprzestrzeni Malamenta-Hogartha lub na orbicie wokół obracającej się czarnej dziury mógłby teoretycznie wykonywać obliczenia nieturingowe dla obserwatora wewnątrz czarnej dziury. Dostęp do CTC może pozwolić na szybkie rozwiązanie problemów związanych z PSPACE-kompletnością , klasą złożoności, która, chociaż rozstrzygalna według Turinga, jest ogólnie uważana za niewykonalną obliczeniowo.

Modele kwantowe

Niektórzy uczeni przypuszczają, że system mechaniki kwantowej , który w jakiś sposób wykorzystuje nieskończoną superpozycję stanów, może obliczyć funkcję nieobliczalną . Nie jest to możliwe przy użyciu standardowego qubit -Model kwantowy komputer , ponieważ udowodniono, że regularne komputer kwantowy jest PSPACE obniżkom (komputer kwantowy działa w czasie wielomianowym mogą być symulowane przez klasycznego komputera pracującego w wielomianowym przestrzeni ).

Systemy „ostatecznie poprawne”

Niektóre fizycznie możliwe do zrealizowania systemy zawsze w końcu zbiegną się z poprawną odpowiedzią, ale mają tę wadę, że często zwracają nieprawidłową odpowiedź i trzymają się nieprawidłowej odpowiedzi przez nieobliczalnie długi czas, zanim w końcu wrócą i poprawią błąd.

  • W połowie lat sześćdziesiątych E Mark Gold i Hilary Putnam niezależnie zaproponowali modele wnioskowania indukcyjnego (odpowiednio „ograniczające funkcjonały rekurencyjne” i „predykaty prób i błędów”). Modele te umożliwiają „nauczenie się w granicach” pewnych nierekurencyjnych zbiorów liczb lub języków (w tym wszystkich rekurencyjnie przeliczalnych zbiorów języków); podczas gdy z definicji maszyna Turinga może zidentyfikować tylko rekurencyjne zestawy liczb lub języków. Podczas gdy maszyna ustabilizuje się do poprawnej odpowiedzi na dowolnym uczącym się zestawie w pewnym skończonym czasie, może zidentyfikować go jako poprawny tylko wtedy, gdy jest rekurencyjny; w przeciwnym razie poprawność jest ustalana tylko przez uruchomienie maszyny w nieskończoność i zauważenie, że nigdy nie zmienia swojej odpowiedzi. Putnam zidentyfikował tę nową interpretację jako klasę predykatów „empirycznych”, stwierdzając: „jeśli zawsze „założymy”, że ostatnio wygenerowana odpowiedź jest poprawna, popełnimy skończoną liczbę błędów, ale ostatecznie otrzymamy poprawną odpowiedź. (Zauważ jednak, że nawet jeśli dotarliśmy do prawidłowej odpowiedzi (koniec ciągu skończonego), nigdy nie jesteśmy pewni, że mamy poprawną odpowiedź.)” Artykuł LK Schuberta z 1974 r. „Iterated Limiting Recursion and the Program Minimization Problem” badał skutki iteracji procedury ograniczającej; pozwala to na obliczenie dowolnego predykatu arytmetycznego . Schubert napisał: „Intuicyjnie, iterowana identyfikacja ograniczająca może być uważana za wnioskowanie indukcyjne wyższego rzędu wykonywane wspólnie przez stale rosnącą społeczność maszyn wnioskowania indukcyjnego niższego rzędu”.
  • Sekwencja symboli jest obliczalna w limicie, jeśli istnieje skończony, prawdopodobnie nie zatrzymujący się program na uniwersalnej maszynie Turinga, który przyrostowo wyprowadza każdy symbol sekwencji. Obejmuje to rozwinięcie dwuczłonowe π i każdej innej obliczalnej liczby rzeczywistej , ale nadal wyklucza wszystkie nieobliczalne liczby rzeczywiste. „Jednotonowe maszyny Turinga” tradycyjnie używane w teorii rozmiaru opisu nie mogą edytować swoich poprzednich wyników; uogólnione maszyny Turinga, jak zdefiniował Jürgen Schmidhuber , kan. Definiuje konstruktywnie opisywane sekwencje symboli jako te, które mają skończony, nie zatrzymujący się program działający na uogólnionej maszynie Turinga, tak że każdy symbol wyjściowy ostatecznie zbiega się; to znaczy, nie zmienia się już po pewnym skończonym początkowym przedziale czasu. Z powodu ograniczeń ujawnionych po raz pierwszy przez Kurta Gödela (1931), może być niemożliwe przewidzenie samego czasu zbieżności za pomocą programu zatrzymującego, w przeciwnym razie problem zatrzymania mógłby zostać rozwiązany. Schmidhuber () używa tego podejścia do zdefiniowania zestawu formalnie możliwych do opisania lub konstruktywnie obliczalnych wszechświatów lub konstruktywnych teorii wszystkiego . Uogólnione maszyny Turinga mogą ostatecznie doprowadzić do poprawnego rozwiązania problemu zatrzymania poprzez ocenę sekwencji Speckera .

Analiza możliwości

Wiele propozycji hiperobliczeń sprowadza się do alternatywnych sposobów odczytywania wyroczni lub funkcji porad wbudowanych w klasyczną maszynę. Inne umożliwiają dostęp do wyższego poziomu hierarchii arytmetycznej . Na przykład superzadaniowe maszyny Turinga, przy zwykłych założeniach, byłyby w stanie obliczyć dowolny predykat w stopniu tabeli prawdy zawierający lub . Natomiast rekurencja ograniczająca może obliczyć dowolny predykat lub funkcję w odpowiednim stopniu Turinga , o którym wiadomo, że jest . Gold wykazał ponadto, że ograniczenie częściowej rekurencji pozwoliłoby na dokładne obliczenie predykatów.

Model Obliczalne predykaty Uwagi Referencje
superzadaniowość tt( ) zależny od obserwatora zewnętrznego
ograniczanie/próby i błędy
iterowane ograniczanie ( k razy)
Blum-Shub-Smale maszyna nieporównywalne z tradycyjnymi obliczalnymi funkcjami rzeczywistymi
Czasoprzestrzeń Malamenta-Hogartha HYP zależny od struktury czasoprzestrzeni
analogowa sieć neuronowa rekurencyjna f jest funkcją doradczą podającą wagi połączeń; rozmiar jest ograniczony przez czas wykonania
nieskończony czas maszyna Turinga Zbiory arytmetyczne quasi-indukcyjne
klasyczna rozmyta maszyna Turinga dla dowolnej obliczalnej normy t
zwiększenie funkcji wyrocznia dla modelu jednosekwencyjnego; są ponownie

Krytyka

Martin Davis w swoich pismach na temat hiperobliczeń odnosi się do tego tematu jako do „mitu” i przedstawia kontrargumenty na rzecz fizycznej realizacji hiperobliczeń. Jeśli chodzi o jej teorię, przeciwstawia się twierdzeniom, że jest to nowa dziedzina powstała w latach 90. XX wieku. Ten punkt widzenia opiera się na historii teorii obliczalności (stopnie nierozwiązywalności, obliczalność nad funkcjami, liczby rzeczywiste i porządkowe), jak również wspomniano powyżej. W swojej argumentacji robi uwagę, że wszystkie hiperobliczenia to niewiele więcej niż: „ jeśli nieobliczalne dane wejściowe są dozwolone, wtedy nieobliczalne dane wyjściowe są osiągalne ”.

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki