Gibt es einen Begriff der Berechenbarkeit für andere Mengen als die natürlichen Zahlen?

Gibt es einen Begriff der Berechenbarkeit für andere Mengen als die natürlichen Zahlen? Nehmen wir zum Zwecke der Argumentation die Mengen $S$ , die mit übereinstimmen $\mathbb{N}$.

Es ist verlockend zu sagen "Ja, es sind jene Funktionen der Form $g \circ f \circ g^{-1}$ wobei $g$ eine beliebige Bijektion $\mathbb{N} \to S$ und $f$ eine beliebige berechenbare Funktion $\mathbb{N} \to \mathbb{N}$ ". Ich bin aus zwei Gründen vorsichtig mit dieser Definition.

1. Es privilegiert $\mathbb{N}$ gegenüber anderen zählbaren Mengen. Warum ist $\mathbb{N}$ Besonderes, wenn es darum geht, Berechenbarkeit zu definieren? Ich möchte eine "koordinatenfreie" Definition der Berechenbarkeit ohne Bezugnahme auf eine privilegierte Menge auf die gleiche Weise wie eine "koordinatenfreie" Definition eines linearen Algebra-Konzepts ohne Bezugnahme auf eine privilegierte Basis.

2. Es wirft Fragen zur Wahl von $g$ . Ich vermute, dass es möglich sein könnte, Widersprüche durch besonders pathologische Entscheidungen von $S$ und $g$ . Wenn ich zum Beispiel $S = \mathbb{N}$ und wähle, ist $g$eine nicht berechenbare Bijektion wirklich der Fall, dass $g \circ f \circ g^{-1}$ für alle berechenbaren berechenbar ist $f$?

   Es ist verlockend, in der Definition zu verlangen, dass $g$ berechenbar ist, aber das wirft leider die Frage auf.

Gibt es eine allgemeine Möglichkeit, die Berechenbarkeit für andere zählbare Mengen als $\mathbb{N}$ ?

Diese Frage ist nicht auf Forschungsebene, aber da sie Antworten erhält, möchte ich eine Antwort anbieten, die die Dinge tatsächlich ein wenig aufklären und Referenzen liefern kann.

Es gibt einen ganzen Bereich der theoretischen Informatik, der die Berechenbarkeit in Analyse, Algebra und Topologie untersucht. Von zentraler Bedeutung ist der Begriff der Berechenbarkeit für reelle Zahlen. Tatsächlich beginnt Turings Originalarbeit über Turing-Maschinen mit dem folgenden Satz:

Die "berechenbaren" Zahlen können kurz als die reellen Zahlen beschrieben werden, deren Ausdrücke als Dezimalzahl mit endlichen Mitteln berechenbar sind.

Manchmal lohnt es sich, zur Quelle zurückzukehren.

Es gibt verschiedene Möglichkeiten, die Berechenbarkeit für allgemeine Mengen einzurichten, von denen eine die allgemeinste die Realisierbarkeitstheorie ist . Die Idee der Realisierbarkeitstheorie geht auf Kleenes Aufsatz über die Interpretation der intuitionistischen Zahlentheorie von 1945 zurück, wurde jedoch seitdem verallgemeinert und zu einem kleinen Zweig der Berechenbarkeit mit einer guten Mischung aus Kategorietheorie entwickelt, siehe zum Beispiel Jaap van Oostens Buch "Realisierbarkeit: eine Einführung in seine kategoriale Seite" (Studies in Logic and the Foundations of Mathematics, Bd. 152, Elsevier, 2008).

Lassen Sie mich die Idee der Realisierbarkeit sehr kurz beschreiben und Ihre "koordinatenfreie" Anforderung später diskutieren. Beginnen Sie mit einem Rechenmodell wie Turing-Maschinen, dem $\lambda$ Kalkül, einer Programmiersprache oder einer anderen partiellen kombinatorischen Algebra (Sie können sogar bestimmte topologische Räume als "Rechenmodelle" betrachten, dieses Zeug ist allgemein ). Betrachten wir der Vollständigkeit halber Turing-Maschinen. Wir codieren Turing-Maschinen nach natürlichen Zahlen, aber beachten Sie, dass ich ein anderes Berechnungsmodell hätte verwenden können, sodass Sie nicht davon ausgehen sollten , dass die Verwendung von $\mathbb{N}$ hier in irgendeiner Weise wesentlich ist. (Andere Möglichkeiten sind: die Potenz natürlicher Zahlen, unendliche Folgen natürlicher Zahlen, die Syntax der untypisierten Zahlen$\lambda$ Kalkül, bestimmte Kategorien von Spielen usw.)

$X$$\Vdash_X$$\mathbb{N}$$X$x ∈ X n ∈ N n ⊩ X x n x ∈ X.$x \in X$$n \in \mathbb{N}$$n \Vdash_X x$$n$$x \in X$

Gegeben seien zwei Baugruppen und , ein Kennfeld wird realisiert (oder "berechenbaren") , wenn es eine Turingmaschine , so dass, wann immer dann endet und . Dies ist wiederum eine direkte Transliteration dessen, was es informell bedeutet, eine abstrakte Funktion zu "programmieren" : Die entsprechende Turing-Maschine stellt Daten dar, was auch immer mit den entsprechenden Elementen tut.$(X, {\Vdash_X})$$(Y, {\Vdash_Y})$$f : X \to Y$T n ⊩ X x T ( n ) T ( n ) ⊩ Y f ( x ) f f$T$$n \Vdash_X x$$T(n)$$T(n) \Vdash_Y f(x)$$f$$f$

Baugruppen können zu realisierbaren Topos erweitert werden . Ein Topos ist ein Modell der intuitionistischen Mathematik höherer Ordnung. Dies sagt uns, dass jedes Realisierbarkeitstopos (es gibt eines für jedes Berechnungsmodell) viele interessante Objekte enthält. Zum Beispiel enthält es ein Objekt mit reellen Zahlen, wodurch wir auf reelle Zahlen berechenbar sind. Es enthält aber auch viele andere Objekte wie Hilbert-Räume, Banach-Räume, Räume mit glatten Karten usw. Sie haben nach einer anderen berechenbaren Struktur gefragt, aber Sie haben etwas viel Besseres erhalten: ganze mathematische Welten der Berechenbarkeit.

Da Kategorietheorie und Topos beängstigend sein können und ein gewisses Maß an technischen Kenntnissen in Berechenbarkeitstheorie, Kategorietheorie und Logik erfordern, könnten wir auch in nur einem konkreten Topos arbeiten, aber wir drücken alles auf konkrete, nicht abstrakte Weise aus. Eine besonders gute Berechnungswelt ergibt sich aus Kleenes Funktionsrealisierbarkeit und wird als berechenbare Analyse bezeichnet .

Lassen Sie mich die Anforderung "koordinatenfrei" kommentieren:

• Das Umschalten zwischen Rechenmodellen bietet verschiedene Arten von berechenbaren Welten. Dies ist ein bisschen wie das Umschalten zwischen verschiedenen Feldern, was verschiedene Arten der linearen Algebra ergibt.

• Eine Menge kann mit vielen Berechenbarkeitsstrukturen , genau wie eine Menge von Vektoren viele Basen hat. Während alle Basen äquivalent sind, sind nicht alle Berechenbarkeitsstrukturen auf rechnerisch äquivalent.$X$⊩ X X.$\Vdash_X$$X$

• Wenn wir konkret mit Berechenbarkeitsstrukturen , ist das ein bisschen wie mit Matrizen in der linearen Algebra. Es kann sehr nützlich sein, ist aber nicht abstrakt.$(X, {\Vdash_X})$

• Um "koordinatenfrei" zu arbeiten, arbeiten wir in einem realisierbaren Topos und nutzen die Kraft der Kategorietheorie (ja, es ist ein Klischee, aber es funktioniert).

• Wir können sogar "weltfrei" arbeiten: Mathematik in intuitionistischer Logik entwickeln und dann die Ergebnisse in realisierbaren Aufgaben interpretieren.

Die beiden folgenden Arbeiten entwickeln einen Begriff der Berechenbarkeit für beliebige Mengen. Interessanterweise kann für dieses Berechnungsmodell sogar ein Begriff der Komplexitätstheorie definiert werden.

Cobham-rekursive Mengenfunktionen und schwache Mengen-Theorien Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Teilmengengebundene Rekursion und ein Schaltungsmodell für Cobham-rekursive Mengenfunktionen Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Es gibt ein Konzept der Komplexität und Berechnung über die Realitäten. Ein Lehrbuch, auf das ich Sie verweisen möchte, lautet: https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

Ich kenne ein Labor, das dies speziell untersucht: https://complexity.kaist.ac.kr/

Dies ähnelt der Definition der Berechenbarkeit von Turing-Maschinen und dem sofortigen Vergessen von Turing-Maschinen. Da sich herausstellt, dass eine Turing-Maschine eine ebenso gute Definition wie jede andere ist, verwenden wir sie als Anker für eine gesamte Äquivalenzklasse von Modellen, und wir erhalten dieselbe Klasse, unabhängig davon, aus welchem ​​Element wir sie generieren. Grundsätzlich ist dies die Church-Turing-These, die den Satz berechenbarer Bitfolgen definiert.

In ähnlicher Weise zu Berechenbarkeit auf einem anderen Satz zu definieren , ankern wir es mit einer bestimmten Teilfunktion von Bit - Strings zu . Tatsächlich spielt es keine Rolle, ob es sich bei dieser Funktion um eine Bijektion oder eine Injektion oder eine andere Art von Funktion handelt (für den Fall, dass wir nicht wirklich möchten, dass es sich um eine Injektion handelt, betrachten Sie eine Gruppe, die durch ihre Darstellung definiert ist und keine hat eine einzigartige Darstellung für seine Elemente). Es muss nicht einmal eine Vermutung sein, wenn wir zulassen, dass Singleton-Mengen nicht berechenbar sein können. Indem wir diese Funktion mit einer berechenbaren Bijektion von Bitfolgen zu Bitfolgen zusammensetzen (ein bereits definiertes Konzept), erhalten wir eine Definition der Berechenbarkeit für$S$$S$$S$Das ist in Bezug auf die Funktion, die wir ursprünglich ausgewählt haben, unveränderlich (solange wir etwas Vernünftiges ausgewählt haben). Das heißt, eine CT - These für unser Set . Wenn wir jedoch keine vernünftige Funktion auswählen, erhalten wir eine andere Definition der Berechenbarkeit.$S$

Diese Funktion dient auch dazu, die Berechenbarkeit anderer Funktionen mit einer Domäne oder einem Bereich gleich . Durch den Bereich Ändern , hält die Domäne als , erhalten wir auch eine -invariant Definition von Kolmogorov Komplexität für . Und wir können endlich sagen, dass die von uns gewählte Funktion selbst berechenbar ist.$S$$S$$\{0,1\}^*$$O(1)$$S$

Ich denke, die Antwort auf Ihre Frage lautet NEIN. Wir müssen die Berechenbarkeit für jede Menge definieren, über die wir sprechen möchten, da es nicht äquivalente Definitionen gibt. Abgesehen von einer sehr technischen oder pädagogischen Diskussion sollte dies nicht notwendig sein, da sich eine vernünftige Person eine vernünftige Definition unabhängig vorstellen kann.

Aber warte, lass eine zählbar unendliche Menge sein, und das war's. Was ist unsere vernünftige Definition der Berechenbarkeit für ? Zu wissen, dass die Menge der Bijektionen zwischen und nicht leer ist, sagt uns nicht, welche vernünftig sind. Wir haben kein Glück ohne weitere Details.$S$$S$$S$$\{0,1\}^*$

Und wir können auf mehrere inäquivalente, aber gleichermaßen vernünftige Alternativen stoßen. Angenommen, jeder Baum hat eine bestimmte Anzahl roter und eine bestimmte Anzahl grüner Blätter, und für jedes gibt es genau einen Baum mit roten Blättern, und zwar für jedes Es gibt genau einen Baum mit grünen Blättern. Beide Bijektionen sind in dem Sinne vernünftig, dass wir die Blätter zählen und die Farben unterscheiden können, und wir können ziellos durch den Wald gehen und Blätter auf Bäumen zählen, bis wir den Baum mit genau grünen Blättern oder den mit$r \in \mathbb{N}$$r$$g \in \mathbb{N}$$g$$23$$23$Rote Blätter. Es ist nicht klar, ob ein Baum anhand seiner Anzahl roter oder grüner Blätter identifiziert werden soll, da diese Auswahl zu ungleichen Definitionen der Berechenbarkeit für Baumgruppen führt. Wenn wir stattdessen unsere Definition durch Kombinieren der Zählungen mit einem berechenbaren Paarungsfunktions-Bijektiv von bis (mit entsprechend definierter Berechenbarkeit für ) vornehmen, identifiziert dies auch jedes eindeutig Baum, aber die Situation ist noch schlimmer, weil dies keine Bijektion zwischen Bäumen und , jetzt sind vielleicht alle berechenbaren Baumgruppen endlich!$\mathbb{N}^2$$\mathbb{N}$$\mathbb{N}^2$$\mathbb{N}$

Um die gesamte Diskussion zu vermeiden, sollte nicht nur verstanden werden, dass es eine vernünftige Definition der Berechenbarkeit für die betreffende Menge gibt, sondern auch, dass es genau eine Klasse vernünftiger Definitionen gibt.

Ich denke, die Situation wird viel interessanter, wenn wir die zeitliche Komplexität ins Bild bringen. Selbst wenn wir nur ganze Zahlen berücksichtigen, sind unsere Entscheidungen wichtiger. Was wäre zum Beispiel, wenn wir jede Zahl als Summe von vier Quadraten darstellen wollten? Wir können eine solche Darstellung ausgehend von einer Basisdarstellung in der erwarteten quadratischen Zeit mit Zugang zur Zufälligkeit finden. Oder stattdessen als Liste seiner Primfaktoren, die möglicherweise in Polynomzeit berechnet werden können oder nicht. In dem Maße, in dem wir harte Darstellungen zulassen, verlieren wir an Präzision in der Zeitkomplexität. Zum Beispiel können wir nicht sinnvoll sagen, dass eine Funktion in quadratischer Zeit berechenbar ist, wenn wir eine Darstellung vonN F : N → $F:\mathbb{N} \rightarrow \mathbb{N}$$\mathbb{N}$Das Konvertieren in oder aus einer Basisdarstellung kann mehr als quadratische Zeit erfordern. Ich denke, diese Perspektive zeigt, dass die Basisdarstellung ein etwas willkürlicher Standard ist. (Standard in dem Sinne, dass die Basisdarstellung das ist, was jeder im Sinn hat, wenn er etwas sagt wie " ist in quadratischer Zeit berechenbar", wenn das zugrunde liegende Modell ein Bit berechnet Strings von Bit Strings und wir sollen die Bedeutung ableiten.)$F:\mathbb{N} \rightarrow \mathbb{N}$