Geometryczna interpretacja obliczeń

Będąc fizyką, zostałem przeszkolony, aby patrzeć na wiele problemów z geometrycznego punktu widzenia. Na przykład geometria różniczkowa rozmaitości w układach dynamicznych itp. Kiedy czytam podstawy informatyki, zawsze staram się znaleźć interpretacje geometryczne. Jak wiarygodna geometryczna interpretacja zbiorów rekurencyjnie wyliczalnych (pracowałem nad częścią, w której próbowałem połączyć je z geometrią algebraiczną, wykorzystując równoważność z zestawami diofantycznymi, ale połączenie wydawało się wymuszone i nie mogłem znaleźć „naturalnego” wyrażenia faktów w tym sformułowanie) lub piękny wynik geometryczny dla prostego algorytmu do sortowania liczb. Chociaż nie jestem ekspertem, przeczytałem ankiety na temat teorii złożoności geometrycznej i jest to z pewnością interesujący program, ale bardziej interesuje mnie geometryczny widok niezwykle podstawowych pojęć, takich jak dynamika maszyny Turinga, rachunku Lambda lub struktury ( un) zestawy obliczalne (zamiast konkretnych problemów). Czy znalezienie struktury geometrycznej w tych obiektach jest beznadziejne, czy można oczekiwać zawiłych rezultatów? Czy istnieje sformułowanie TCS, które traktuje go geometrycznie?

Semantykę programów komputerowych można rozumieć geometrycznie na trzy różne (i pozornie niezgodne) sposoby.

• Najstarsze podejście opiera się na teorii domen . Intuicja stojąca za teorią domen wynika z asymetrii stojącej za terminacją i nieterminacją.

  Podczas długotrwałego traktowania programów (tzn. Patrząc tylko na ich zachowanie we / wy, a nie na ich wewnętrzną strukturę), zawsze można w skończonym czasie potwierdzić, że program się zatrzymuje - wystarczy poczekać, aż się zatrzyma. Nie można jednak potwierdzić, że program się nie zatrzymuje, ponieważ bez względu na to, jak długo czekasz, zawsze istnieje program zatrzymujący, który będzie działał przez kilka kolejnych kroków, niż czekałeś.

  W rezultacie zatrzymanie i zapętlenie można postrzegać jako tworzenie przestrzeni topologicznej ( przestrzeni Sierpińskiego ). Podnosi to bogatsze pojęcia obserwacji (poprzez topologię Scotta), dzięki czemu można interpretować programy jako elementy przestrzeni topologicznych. Przestrzenie te są na ogół dość zaskakujące z tradycyjnego punktu widzenia - domeny na ogół nie są Hausdorffem.

  Najlepszym wprowadzeniem topologicznym, jakie znam te idee, jest krótka i niezwykle dostępna Topologia Steve'a Vickersa za pośrednictwem logiki . Można to rozumieć jako rodzaj rozgrzewki dla znacznie groźniejszych Kamiennych Przestrzeni Petera Johnstone'a .

  Jeśli szukasz notatek z wykładów online, pozwól, że zasugeruję syntetyczną topologię typów danych i klasycznych przestrzeni Martina Escardo .

• Kolejny pogląd wynika z teorii współbieżności. Program współbieżny może być rozumiany jako posiadający wiele poprawnych wykonań (sekwencji stanów), w zależności od sposobu rozwiązywania ras. Następnie zestaw wykonań można postrzegać jako przestrzeń, a każdą możliwą sekwencję stanów rozumieć jako ścieżkę przez tę przestrzeń. Następnie można zastosować metody z topologii algebraicznej i teorii homotopii w celu uzyskania niezmienników dotyczących wykonania programu.

  Nir Shavit i Maurice Herlihy wykorzystują ten pomysł, aby udowodnić niemożność zastosowania niektórych algorytmów rozproszonych, za które zdobyli nagrodę Gödela w 2004 roku. (Patrz Topologiczna struktura obliczeń asynchronicznych ). Eric Goubault ma artykuł z ankietą wyjaśniający odpowiednie pomysły w niektórych perspektywach geometrycznych w teorii współbieżności .

• Ostatnio zaobserwowano, że struktura typu tożsamości w teorii typów zależnych bardzo ściśle odpowiada pojęciu typu homotopii w teorii homotopii - tak blisko, że tak naprawdę teoria typów zależnych może być faktycznie postrzegana jako rodzaj „syntetyczna teoria homotopty”! (Vladimir Voevodsky żartował, że spędził kilka lat opracowując nowy rachunek teorii homotopii, aby odkryć, że jego koledzy z wydziału CS już uczyli go studentów).

  Zobacz link cody powyżej do książki teorii typów homotopii .

Co ciekawe, te trzy poglądy wydają się ze sobą niezgodne lub przynajmniej bardzo trudne do pogodzenia. Teoria typów zależnych jest językiem całkowitym, więc nie ma w niej końca (i topologii Scotta). Jest także zbieżny, więc widok obliczeń jako przestrzeni również nie powstaje. Podobnie formułowanie współbieżności w kategoriach teorii domen okazało się okropnie trudne, a całkowicie satysfakcjonujący rachunek jest nadal otwartym problemem.

Tak się składa, że ​​ostatnio rozwinięto teorię typów zależnych , w której typy, które tradycyjnie stanowią niezmienność statyczną programu komputerowego, można interpretować jako przestrzeń topologiczną lub raczej klasę równoważności takich spacje ( typ homotopii ).

Było to przedmiotem intensywnych badań w ciągu ostatnich kilku lat, których zwieńczeniem była książka .

$\lambda$

Zdajesz sobie sprawę z GCT, ale możesz nie być świadomy wcześniejszej pracy Mulmuleya nad pokazaniem rozdziału między podzbiorem obliczeń PRAM i P, który wykorzystuje geometryczne pomysły na to, jak obliczenia można postrzegać jako rzeźbienie przestrzeni.

Wiele dolnych granic problemów w algebraicznym modelu drzewa decyzyjnego sprowadza się do wnioskowania na temat topologii leżących u podstaw przestrzeni rozwiązań (liczby Betti są wyświetlane jako odpowiedni parametr).

W pewnym sensie WSZYSTKIE optymalizacje są geometryczne: programy liniowe polegają na znalezieniu najniższego punktu politopu w wysokich wymiarach, SDP są funkcjami liniowymi w przestrzeni macierzy półfinałowych i tak dalej. Geometria jest tu często używana w projektowaniu algorytmów.

W tym temacie istnieje długi i głęboki związek między naszą zdolnością do optymalizacji niektórych funkcji na wykresach a naszą zdolnością do osadzania przestrzeni metrycznych w określonych przestrzeniach normowanych. To jest teraz obszerna literatura.

Wreszcie, w ostatnich latach zainteresowanie budzą tak zwane mechanizmy podnoszenia i projektowania do rozwiązywania problemów optymalizacyjnych, które w dużym stopniu wykorzystują leżącą u podstaw geometrię i wyciągi do przestrzeni o większych wymiarach: pojęcia z gry geometrii algebraicznej ważną rolę tutaj.

$T_1$

Jednym ze sposobów zrozumienia związku między przetwarzaniem informacji (znanym również jako „obliczenia”) a geometrią jest to, że przetwarzanie informacji poprzedza geometrię. Ten pogląd powinien być znany z niektórych części fizyki. Na przykład w teorii względności badamy zarówno przyczynową strukturę czasoprzestrzeni (jej przetwarzanie informacji), jak i jej geometryczną strukturę . Wielu uważa, że ​​ta ostatnia jest bardziej podstawowa niż pierwsza.

Połączenia te zostały zauważone w przeszłości, a kilka lat temu podjęto próbę połączenia informatycznych aspektów informatyki z teorią względności. Jednym z zadań, które ludzie chcieli rozwiązać, było: zaczynając od struktury przyczynowej czasoprzestrzeni (która jest tylko częściowym porządkiem czasoprzestrzeni), zrekonstruować topologię czasoprzestrzeni, a być może także geometrię. Odzyskiwanie topologii z częściowego porządku jest czymś, w czym teoria domen jest dobra, więc odniosła pewien sukces.

Bibliografia:

• Struktury obliczeniowe dla modelowania przestrzeni, czasu i przyczynowości , Seminarium Dagstuhl 06341, 20–25 sierpnia 2006

• Key Martin i Prakash Panangaden: Geometria czasoprzestrzeni ze struktury przyczynowej i pomiar

$U$

twórczo interpretując swoje pytanie, przychodzą na myśl inne możliwości niż GCT. Jednym ze sposobów jest poszukiwanie nierozstrzygalnych problemów (zwanych kompletnością Turinga), które są dość wszechobecne.

• aperiodic Dachówka samolotu i dachówka Penrose . dowiedziono, że kwestia aperodycznej dachówki samolotu jest nierozstrzygnięta.

• Automaty komórkowe, które również coraz częściej wykazują głębokie powiązania z fizyką, wiele powiązanych nierozwiązywalnych problemów, udowodniono, że są kompletne i są naturalnie interpretowane jako (i konwertowane między) tablice obliczeniowe TM.

• algorytmy jak fraktale . obszar bardziej nierozwinięty (tj. aktywne / trwające badania!), ale różne nierozstrzygnięte pytania, na przykład złożone zagadnienie$(x,y)$czy to jest w zestawie Mandelbrota ?

• Nierozstrzygalność w układach dynamicznych (Hainry), ponownie czasami ściśle związana z fizyką. układy dynamiczne mają na ogół wielowymiarową interpretację geometryczną.

• Języki programowania wizualnego . program może być postrzegany jako typ (skierowany?) wykresu z różnymi typami wierzchołków (np. operacja warunkowa, arytmetyczna) itp.