Die Kategorie der Turingmaschinen?

Haftungsausschluss: Ich weiß sehr wenig über Komplexitätstheorie.

Es tut mir leid, aber es gibt wirklich keine Möglichkeit, diese Frage zu stellen, ohne (schrecklich) präzise zu sein:

Was sollen die Morphismen in "der" Kategorie der Turingmaschinen sein?

Dies ist offensichtlich subjektiv und hängt von der Interpretation der Theorie ab. Daher sollte eine Antwort auf diese Frage im Idealfall auch Beweise und Argumente liefern, die die Antwort stützen.

Ich möchte den Punkt betonen, dass ich nach einer Kategorie von Turingmaschinen suche und nicht zum Beispiel nach formalen Sprachen . Insbesondere denke ich, dass meine Morphismen feinere Informationen als Verkleinerungen oder ähnliches enthalten sollten (ich bin mir jedoch nicht sicher).

Natürlich würde ich gerne wissen, was es ist, wenn es in der Literatur bereits eine bekannte und verwendete Kategorie gibt.

cc.complexity-theory turing-machines ct.category-theory Saal Hardali
quelle

Sie haben es selbst gesagt - berechenbare Funktionen.

Yuval Filmus

@Raphael die Sache ist, Sie definieren nie wirklich eine Struktur, bis Sie es in eine Kategorie setzen. In diesem Fall werden die unwesentlichen Merkmale der spezifischen Definition entfernt.

Saal Hardali

@SaalHardali Denken Sie daran, dass nicht jeder das Heilsversprechen der Kategorietheoretiker unterschreibt. Tatsächlich rollen viele mit den Augen.

Raphael

@JoshuaGrochow Es gibt einen mit

bezeichneten Morphismus von

bis

wenn

reduziert (oder umgekehrt), dh

. Dies gilt beispielsweise für Maschinen, die bei jeder Eingabe anhalten oder nicht, aber keine weitere Ausgabe haben.

f

$f$

T_{1}

$T_1$

T_{2}

$T_2$

f

$f$

T_{2}

$T_2$

T_{1}

$T_1$

T_{1} (x) = T_{2} (f (x))

$T_1(x) = T_2(f(x))$

Yuval Filmus

Nebenbei: Warum sollten TMs Objekte sein? Sie könnten auch Morphismen sein.

Martin Berger

Antworten:

Saal Hardali erwähnte, dass er wollte, dass eine Kategorie von Turingmaschinen Geometrie (oder zumindest Homotopietheorie) ausführt. Es gibt jedoch viele verschiedene Möglichkeiten, ähnliche Ziele zu erreichen.

Es gibt eine sehr starke Analogie zwischen Berechenbarkeit und Topologie. Die Intuition ist, dass Terminierung / Nicht-Terminierung wie der Sierpinski-Raum ist, da Terminierung endlich beobachtbar (dh offen) ist und Nicht-Terminierung nicht (nicht offen) ist. Siehe Martin Escardos Vorlesungsunterlagen Synthetische Topologie von Datentypen und klassischen Räumen für eine gemäßigte sanfte, aber umfassende Einführung in diese Ideen.
Bei gleichzeitiger und verteilter Berechnung ist es oft nützlich, sich die möglichen Ausführungen eines Programms als Raum vorzustellen, und dann können verschiedene Synchronisationsbeschränkungen als homotopische Eigenschaften des Raums ausgedrückt werden. (Die Tatsache, dass die Ausführung eine zeitliche Reihenfolge hat, scheint eher eine gerichtete Homotopietheorie als eine gewöhnliche Homotopietheorie zu erfordern.)

Weitere Informationen finden Sie in Eric Goubaults Artikel Einige geometrische Perspektiven zur Theorie der Parallelität . Siehe auch Maurice Herlihy und Nir Shavits mit dem Goedel-Preis ausgezeichnetes Papier The Topological Structure of Asynchronous Computability , das einige seit langem offene Probleme in der Theorie der verteilten Programmierung gelöst hat.
Eine dritte Idee kommt über die Homotopietypentheorie, über die Entdeckung, dass die Martin-Löf-Typentheorie (wahrscheinlich?) Eine syntaktische Darstellung (im Sinne von Generatoren und Beziehungen) der Theorie der Omega-Gruppoiden ist, dh der Modelle der Abstraktion Homotopietheorie. Die beste Einführung in diese Ideen ist das Buch zur Homotopietypentheorie .

Beachten Sie, dass alle diese Ideen sehr unterschiedlich sind, aber immer noch geometrische Intuitionen verwenden! Und es gibt noch andere, die ich nicht kenne, wie die Verwendungen, die in der geometrischen Komplexitätstheorie auftreten, und die Art und Weise, wie die Schaltkreistheorien im Sinne der (Co) Homologietheorie von Graphen beschrieben werden können .

Grundsätzlich ist Geometrie bei CS ein Werkzeug - Sie formalisieren damit Ihre Intuitionen, sodass Sie durch die enorme Menge an Arbeit, die Sie damit geleistet haben, eine Hebelwirkung erzielen können. Aber es ist ein Ideenverstärker, kein Ersatz für Ideen!

Neel Krishnaswami
quelle

Wenn es sich bei Ihren Objekten um Turingmaschinen handelt, gibt es verschiedene sinnvolle Möglichkeiten für Morphismen. Beispielsweise:

1) Betrachten Sie Turing-Maschinen als die Automaten, die sie sind, und betrachten Sie die üblichen Morphismen von Automaten (Abbildungen zwischen den Alphabeten und den Zuständen, die miteinander konsistent sind), die ebenfalls entweder die Bewegungen des Bandkopfes (der Bandköpfe) bewahren oder genau umgekehrt sie (z. B. wenn das Quell-TM nach links geht, geht das Ziel-TM nach rechts und umgekehrt).

2a) Betrachten Sie Simulationen oder Bisimulationen .

2b) In ähnlicher Weise können Sie überlegen, wann ein TM (durch eine berechenbare Funktion) transformiert werden kann, um das andere zu simulieren. Dies kann auf der Ebene des schrittweisen Verhaltens geschehen, oder, wie Yuval in den Kommentaren angedeutet hat, auf der Ebene des Input-Output, dh ein Morphismus von zu (oder umgekehrt) ist a berechenbar so, dass $T_1$ $T_2$ $f$ $T_1(x) = T_2(f(x))$ $x$

3) Betrachten Sie den Übergangsgraphen der Turing-Maschine (jeder Scheitelpunkt ist eine vollständige Beschreibung des Zustands der Maschine und der Bänder, wobei die gerichteten Kanten den Übergängen entsprechen, die die TM machen würde) und berücksichtigen Sie die Morphismen der Graphen. Für TMs ist dies jedoch eine sehr grobe Beziehung, da die lokale Art der Berechnung im Wesentlichen ignoriert wird (z. B. der Inhalt der Bänder wird ignoriert).

Ich denke , die Frage ist: Was ist es Sie wollen wissen , über TMs oder zu tun mit ihnen? In Ermangelung dessen ist es schwierig, Argumente für eine Definition über eine andere zu liefern, die über die Natürlichkeit hinausgeht (im üblichen Sinne des Wortes, nicht im kategorialen Sinne).

Joshua Grochow
quelle

Ich bin sehr neu in dieser Art von Mathematik. Ich habe in der Vergangenheit über Komplexitätstheorie gelesen, aber erst kürzlich habe ich sie wieder aufgegriffen, als ich jemanden im Internet sah, der behauptete, irgendwie würden kohomologische Techniken im nächsten Jahrhundert in die Komplexitätstheorie einfließen, und das hat mich interessiert. Nach einigem Lesen wurde mir klar, dass ich, abgesehen von einem oberflächlichen Verständnis der Definition einer Turingmaschine, im Grunde keine Ahnung habe, was sie genau codiert. So bin ich zu der Frage gekommen. Man könnte also sagen, dass ich mir auf einer sehr rudimentären Ebene vorstelle, wie Kohomologie in die Komplexitätstheorie eingehen kann.

Saal Hardali

Ich stelle fest, dass dies für jemanden wie mich extrem verfrüht ist, der nur sehr wenig über dieses Thema versteht, und dennoch wollte ich ein bisschen mit dieser Idee in meinem Kopf "Homotopietheorie in der Kategorie der Turingmaschinen" spielen. Ihre Antwort ist nett und ich möchte auf jeden Fall mehr darüber lesen. Vielen Dank.

Saal Hardali

@ SaalHardali: Ich bin gespannt, wo Sie lesen, dass Kohomologie in die Komplexitätstheorie einfließen wird. Ich kann mir zwei Möglichkeiten vorstellen, aber ich sehe noch keine Route über die Homotopietypentheorie (vielleicht, weil ich HoTT noch nicht gut genug verstehe). Die zwei Möglichkeiten, die ich sehen kann: (1) In Distributed Computing ist dies bereits geschehen, nämlich. Herlihy und Rajsbaum und (2) über geometrische Komplexitätstheorie.

Joshua Grochow

Mit der Homotopietheorie bezog ich mich auf die allgemeine Idee, Kategorien mit schwachen Äquivalenzen und weniger HoTT zu studieren. Ich habe es in einer Umfrage über P =? NP gelesen. Es ist nicht schwer zu finden. Ich denke, es wurde von einer der Fragen auf dieser Seite verlinkt. Ich denke, meine erste Vermutung (als Außenseiter) war, dass es vielleicht eine interessante schwache Äquivalenz in einer Kategorie eines Berechnungsmodells gibt, die irgendwie Komplexitätsklassen entspricht, und dann wird das Studium von Funktoren, die unter dieser schwachen Äquivalenz invariant sind, das ausmachen, was ich nenne. " homotopy theorie "das ist wahrscheinlich sehr naiv und ein totaler fehlschlag.

Saal Hardali

Wenn

Sasho Nikolov

Vielleicht interessieren Sie sich auch für die Turing-Kategorien von Robin Cockett und Pieter Hofstra. Aus kategorietheoretischer Sicht ist die Frage "Was ist die Kategorie der Turingmaschinen?" Weniger interessant als "Was ist die kategoriale Struktur, die der Berechnung zugrunde liegt?". So identifizieren Robin und Pieter eine allgemeine Kategorie, die zur Entwicklung der Berechenbarkeitstheorie geeignet ist. Dann gibt es mehrere Möglichkeiten, eine solche Kategorie ausgehend von Turing-Maschinen zu definieren. Warum eine Kategorie, wenn Sie eine ganze Kategorie haben können?

Andrej Bauer
quelle