Geometrische Interpretation der Berechnung

Da ich aus der Physik komme, habe ich gelernt, viele Probleme unter geometrischen Gesichtspunkten zu untersuchen. Zum Beispiel die Differentialgeometrie von Mannigfaltigkeiten in dynamischen Systemen usw. Wenn ich die Grundlagen der Informatik lese, versuche ich immer, geometrische Interpretationen zu finden. Wie eine plausible geometrische Interpretation von rekursiv aufzählbaren Mengen (Ich arbeitete an einem Teil, in dem ich versuchte, sie mit der algebraischen Geometrie zu verbinden, indem ich die Äquivalenz mit diophantinischen Mengen ausnutzte, aber die Verbindung schien erzwungen und ich konnte keinen "natürlichen" Ausdruck der Tatsachen darin finden Formulierung) oder ein schönes geometrisches Ergebnis für einen einfachen Algorithmus zum Sortieren von Zahlen. Obwohl ich kein Experte bin, habe ich Umfragen zur Geometrischen Komplexitätstheorie gelesen und es ist sicherlich ein interessantes Programm, aber ich bin mehr daran interessiert, eine geometrische Sicht auf extrem grundlegende Konzepte wie die Dynamik einer Turing-Maschine, Lambda-Kalkül oder die Struktur von ( un) berechenbare Mengen (statt spezifischer Probleme). Ist es eine hoffnungslose Aufgabe, geometrische Strukturen in diesen Objekten zu finden, oder kann man komplizierte Ergebnisse erwarten? Gibt es eine Formulierung von TCS, die es geometrisch behandelt?

Die Semantik von Computerprogrammen kann geometrisch auf drei verschiedene (und offensichtlich inkompatible) Arten verstanden werden.

• Der älteste Ansatz ist die Domänentheorie . Die Intuition hinter der Domänentheorie ergibt sich aus der Asymmetrie hinter Terminierung und Nicht-Terminierung.

  Wenn Sie Programme ausführlich behandeln (dh nur ihr E / A-Verhalten und nicht ihre interne Struktur betrachten), ist es immer möglich, in endlicher Zeit zu bestätigen, dass ein Programm anhält - Sie warten nur, bis es anhält. Es kann jedoch nicht bestätigt werden, dass ein Programm nicht angehalten wird, da unabhängig von der Wartezeit immer ein angehaltenes Programm einige Schritte länger ausgeführt wird, als Sie gewartet haben.

  Infolgedessen kann das Anhalten und Schleifen als Bildung eines topologischen Raums ( Sierpiński-Raum ) angesehen werden. Dies führt zu umfassenderen Beobachtungsvorstellungen (über die Scott-Topologie), und Sie können damit Programme als Elemente topologischer Räume interpretieren. Diese Räume sind aus traditioneller Sicht in der Regel recht überraschend - Domains sind in der Regel nicht Hausdorff.

  Die beste topologische Einführung, die ich in diese Ideen kenne, ist Steve Vickers 'kurze und extrem zugängliche Topologie über Logic . Es kann als eine Art Aufwärmen für Peter Johnstones bedeutend beeindruckendere Stone Spaces verstanden werden .

  Wenn Sie nach Online-Vorlesungsskripten suchen, schlage ich Martin Escardos Synthetische Topologie von Datentypen und klassischen Räumen vor .

• Eine andere Sichtweise ergibt sich aus der Parallelitätstheorie. Unter einem gleichzeitigen Programm versteht man mehrere gültige Ausführungen (Folgen von Zuständen), je nachdem, wie Rassen aufgelöst werden. Dann kann der Satz von Ausführungen als ein Raum angesehen werden, wobei jede mögliche Folge von Zuständen als Pfad durch diesen Raum verstanden wird. Anschließend können Methoden aus der algebraischen Topologie und der Homotopietheorie angewendet werden, um Invarianten über die Programmausführung abzuleiten.

  Nir Shavit und Maurice Herlihy verwenden diese Idee, um die Unmöglichkeit bestimmter verteilter Algorithmen zu beweisen, für die sie 2004 den Gödel-Preis gewonnen haben. (Siehe Die topologische Struktur der asynchronen Berechnung .) Eric Goubault hat einen Übersichtsartikel verfasst, in dem die relevanten Ideen in Einige geometrische Perspektiven in der Parallelitätstheorie erläutert werden .

• In jüngster Zeit wurde beobachtet, dass die Struktur des Identitätstyps in der Theorie abhängiger Typen sehr eng mit dem Begriff des Homotopietyps in der Homotopietheorie übereinstimmt - so eng, dass die Theorie abhängiger Typen tatsächlich als eine Art von Theorie angesehen werden kann "Synthetische Homotoptietheorie"! (Vladimir Voevodsky hat gescherzt, dass er mehrere Jahre damit verbracht hat, einen neuen Kalkül für die Homotopietheorie zu entwickeln, nur um herauszufinden, dass seine Kollegen in der CS-Abteilung ihn bereits Studenten beigebracht haben.)

  Siehe Codys Link oben auf die Homotopietyp Theorie Buch .

Interessanterweise scheinen diese drei Ansichten unvereinbar oder zumindest sehr schwer miteinander zu vereinbaren. Die Theorie des abhängigen Typs ist eine Gesamtsprache, daher tritt darin keine Nichtbeendigung (und die Scott-Topologie) auf. Es ist auch konfluent, so dass der Blick auf Berechnungen als Räume auch nicht entsteht. In ähnlicher Weise hat es sich als äußerst schwierig erwiesen, Parallelität im Sinne der Domänentheorie zu formulieren, und eine völlig zufriedenstellende Darstellung ist immer noch ein offenes Problem.

Wie es passiert einfach so, gab es in der Theorie der jüngsten Entwicklung gewesen abhängige Arten , in denen eine Art, die traditionell eine statische invariant für ein Computerprogramm darstellen, interpretiert werden kann ein topologischer Raum, oder vielmehr eine sein Äquivalenzklasse eines solchen Leerzeichen (ein Homotopietyp ).

Dies war in den letzten Jahren Gegenstand intensiver Forschungen, die in einem Buch gipfelten .

$\lambda$

Sie kennen GCT, aber Sie kennen möglicherweise nicht Mulmuleys frühere Arbeiten zur Darstellung einer Trennung zwischen einer Teilmenge von PRAM-Berechnungen und P, die geometrische Ideen verwendet, wie eine Berechnung als Aufteilung eines Raums angesehen werden kann.

Viele Untergrenzen für Probleme im algebraischen Entscheidungsbaummodell beschränken sich auf Überlegungen zur Topologie der zugrunde liegenden Räume von Lösungen (Betti-Zahlen werden als relevanter Parameter angezeigt).

In gewisser Hinsicht ist ALLE Optimierung geometrisch: Bei linearen Programmen wird der tiefste Punkt eines Polytops in hohen Dimensionen gefunden, SDPs sind lineare Funktionen über den Raum von semidefiniten Matrizen usw. Die Geometrie wird hier in hohem Maße beim Entwurf von Algorithmen verwendet.

Bei diesem Thema besteht ein langer und tiefer Zusammenhang zwischen unserer Fähigkeit, bestimmte Funktionen in Diagrammen zu optimieren, und unserer Fähigkeit, metrische Räume in bestimmte normierte Räume einzubetten. Dies ist jetzt eine riesige Literatur.

Schließlich gab es in den letzten Jahren ein großes Interesse an sogenannten "Lift-and-Project" -Mechanismen zur Lösung von Optimierungsproblemen, bei denen die zugrunde liegende Geometrie und die Aufzüge in höherdimensionale Räume stark genutzt wurden: Begriffe aus dem algebraischen Geometriespiel eine wichtige Rolle hier.

$T_1$

Eine Möglichkeit, die Beziehung zwischen Informationsverarbeitung (auch als "Berechnung" bezeichnet) und Geometrie zu verstehen, besteht darin, dass die Informationsverarbeitung der Geometrie vorausgeht . Diese Sichtweise sollte aus bestimmten Teilen der Physik bekannt sein. In der Relativitätstheorie untersuchen wir beispielsweise sowohl die kausale Struktur der Raumzeit (ihre Informationsverarbeitung) als auch ihre geometrische Struktur . Viele würden die letztere als grundlegender als die erstere betrachten.

Diese Zusammenhänge wurden in der Vergangenheit bemerkt und vor einigen Jahren wurde versucht, die informationstheoretischen Aspekte der Informatik mit der Relativitätstheorie zu verbinden. Eine der Aufgaben, die die Menschen lösen wollten, war: Ausgehend von der Kausalitätsstruktur der Raumzeit (die nur eine Teilordnung der Raumzeit ist) die Topologie der Raumzeit oder möglicherweise auch die Geometrie zu rekonstruieren. Das Wiederherstellen der Topologie aus einer Teilreihenfolge ist eine Sache, in der die Domänentheorie gut ist, daher gab es einige Erfolge.

Verweise:

• Computerstrukturen zur Modellierung von Raum, Zeit und Kausalität , Dagstuhl Seminar 06341, 20. – 25. August 2006

• Key Martin und Prakash Panangaden: Raumzeitgeometrie aus Kausalstruktur und Messung

$U$

Wenn Sie Ihre Frage kreativ interpretieren, kommen Ihnen einige andere Möglichkeiten als die von GCT in den Sinn. Eine Möglichkeit besteht darin, nach unentscheidbaren Problemen (auch bekannt als Turing-Vollständigkeit) zu suchen, die allgegenwärtig sind.

• aperiodische Kacheln des Flugzeugs & Penrose-Kacheln . Es ist bewiesen, dass die Frage, ob es sich um eine aperodische Kachelung des Flugzeugs handelt, nicht zu entscheiden ist.

• Zelluläre Automaten, von denen auch zunehmend gezeigt wird, dass sie eine tiefe Verbindung zur Physik haben, viele damit zusammenhängende, unentscheidbare Probleme aufweisen, nachweislich vollständig sind und von Natur aus als (und zwischen) TM-Computertableaus interpretiert werden.

• $(x,y)$

• Unentscheidbarkeit in dynamischen Systemen (Hainry), die manchmal eng mit der Physik verbunden sind. Dynamische Systeme weisen im Allgemeinen eine mehrdimensionale geometrische Interpretation auf.

• Visuelle Programmiersprachen . Ein Programm kann als eine Art (gerichteter?) Graph mit verschiedenen Arten von Eckpunkten (z. B. bedingte, arithmetische Operation) usw. angesehen werden.