Warum sind berechenbare Funktionen kontinuierlich?

Ich arbeite daran, ein leicht lesbares Dokument über die Denotationssemantik des Lambda-Kalküls zu schreiben . Dafür stelle ich CPOs, Monotonie und Kontinuität vor. Ein CPO ist eine Menge$M$ mit einer Teilbestellung $\leq$ und ein unteres Element $\bot$erforderlich $\bot$ das kleinste Element in sein $M$ und die Existenz der kleinsten Obergrenze ($\bigsqcup$) für jede Kette $d_0 \leq d_1 \leq d_2 \leq ...$ im $M$. Eine Funktion$f$ zwischen zwei CPOs $M$, $N$ ist monoton, wenn für alle $a, b \in M$ Folgendes gilt:

Eine Funktion $f$ zwischen zwei CPOs $M$, $N$ ist kontinuierlich, wenn es monoton ist und für alle Ketten $d_0 \leq d_1 \leq d_2 \leq \dots$ wir haben

Ich möchte meinen Lesern eine gute Vorstellung von der Bedeutung dieser Definitionen vermitteln. Ich habe jedoch keine, die ich aufschreiben könnte. Nach Glynn Winskel in seinem Buch »Die formale Semantik der Programmiersprachen« (1993),$a \leq b$ muss gelesen werden als $a$ ungefähr $b$ (Seite 72), was bedeutet $b$ hat mindestens so viele Informationen wie $a$. Dies führt zu monotonen Funktionen, die mehr Informationen über die Eingabe in mehr Informationen über die Ausgabe widerspiegeln (Seite 122). Das ist für mich etwas verständlich. Die Erklärung der Kontinuität ist mir jedoch nicht klar:

Wie wir sehen werden, folgt, dass berechenbare Funktionen kontinuierlich sein sollten, aus der Idee, dass das Auftreten einer Informationseinheit in der Ausgabe einer berechenbaren Funktion nur vom Vorhandensein endlich vieler Informationseinheiten in der Eingabe abhängen sollte.

(Seite 73)

Dies ist mir nach dem Lesen des Stream-Beispiels in Abschnitt 8.2 (Seiten 121–123) oder dieser Antwort noch unklar .

Meine letzte Frage lautet also: Wie kann ich meine Leser davon überzeugen, dass berechenbare Funktionen kontinuierlich sind? Warum gibt es keine berechenbare Funktion, die nicht kontinuierlich ist?

Es wäre schön, wenn Sie mir Antworten / Beispiele geben könnten, die keine strenge Einführung der Berechenbarkeit oder der Fixpunkttheorie erfordern, da ich mich nicht auf diese Dinge konzentrieren möchte. Es wäre auch großartig, wenn es nicht notwendig wäre, den Lambda-Kalkül und seine Denotationssemantik im Voraus zu kennen, weil ich Monotonie und Kontinuität vor ihnen einführen möchte (und muss).

EDIT: Mit berechenbar meine ich Turing-berechenbar. Bitte korrigieren Sie mich, wenn ich die Winskels-Definition von berechenbar auf Seite 337 falsch verstehe, da sie nicht explizit als Turing-berechenbar definiert ist, sondern auf äquivalente Weise (zumindest in meinen Augen).

Ich möchte auch auf eine andere Quelle hinweisen, die ich gefunden habe und die versucht, mein Problem zu erklären. Trotzdem verstehe ich das Beispiel nicht, da es im Grunde das gleiche ist wie das Stream-Beispiel von Winskel.

EDIT 2: Es wäre auch ein guter Anfang, um die Sache zu verstehen und zu zeigen, dass jede berechenbare Funktion monoton ist, dh es gibt keine nicht monotone berechenbare Funktion.

Es gibt verschiedene Möglichkeiten zu erklären, dass "berechenbar impliziert kontinuierlich". Ich werde hier zwei solche Erklärungen geben.

Turingmaschinen berechnen fortlaufende Karten

Angenommen, wir haben eine Turing-Maschine, die möglicherweise unendlich viel Eingabe auf ein Eingabeband schreibt. Es schreibt das Ergebnis auf ein Ausgabeband, auf dem die Ausgabezellen einmal geschrieben werden. Es gibt Arbeitsbänder. Die Maschine läuft möglicherweise für immer und füllt die Ausgangszellen. Dies ist als Typ-2- Maschine bekannt. (Das Argument für andere Arten von Maschinen wird ähnlich, aber einfacher sein.)

Folgendes sollte offensichtlich sein: Wenn die Maschine in eine Ausgabezelle schreibt, hängt ihre Arbeitsweise bis zu diesem Punkt nur von einem endlichen Teil des Eingabebandes ab, aus dem einfachen Grund, dass sie in endlich vielen Berechnungsschritten den Eingabekopf nicht hätte bewegen können irgendwann. Daher hätte jedes Eingabeband, das bis zu diesem Zeitpunkt mit dem angegebenen übereinstimmt, dazu geführt, dass die Maschine dieselbe Antwort in dieselbe Ausgabezelle geschrieben hätte.

Dies ist jedoch eine Form der Kontinuität, wenn wir die Räume der Eingabe- und Ausgabebänder mit der richtigen Topologie versehen.

Zuerst setzen wir die Topologie auf das Set $\Sigma$von Symbolen, die auf Bandzellen geschrieben werden können. Dazu wählen wir einfach die diskrete Topologie. Ein Band ist eine unendliche Folge von Symbolen, also ein Element von$\Sigma^\omega$, das ist ein Produkt von $\Sigma$'s. Lassen Sie uns die Produkttopologie darauf setzen.

Denken Sie daran, dass ein grundlegendes offenes Set aktiviert ist $\Sigma^\omega$ denn die Produkttopologie hat die Form $U(a_0, \ldots, a_{n-1}) = \{\alpha \in \Sigma^\omega \mid \forall i < n . \, \alpha_i = a_i\}$, wo $a_0, \ldots, a_i \in \Sigma$. Das heißt, ein offener Basissatz fixiert einen Anfangsabschnitt der Sequenz auf die angegebenen Werte$a_0, \ldots, a_n$.

Jetzt können wir überprüfen, ob die Funktion $f : \Sigma^\omega \to \Sigma^\omega$von der Maschine berechnet ist in der Tat kontinuierlich. Nehmen Sie ein einfaches offenes Set$V = U(a_0, \ldots, a_{n-1})$ und lass $W = f^{-1}(V)$. Wir müssen das überprüfen$W$ist offen. Berücksichtigen Sie zu diesem Zweck alle$\alpha \in W$. Wenn wir eine offene Grundmenge finden$W'$ so dass $\alpha \in W' \subseteq W$Dann sind wir fertig.

weil $\alpha \in W$, wir haben $f(\alpha) \in U$. Also bei Eingabe$\alpha$ Die Maschine erzeugt ein Ausgabeband, das mit beginnt $a_0, a_1, \ldots, a_{n-1}$. Bis es diese Zellen ausschreibt, hat es höchstens die erste inspiziert$k$ Zellen der Eingabe, für einige $k \in \mathbb{N}$. Wir können nehmen$W' := U(\alpha_0, \ldots, \alpha_k)$ und überprüfen Sie das $\alpha \in W' \subseteq W$. Es ist offensichtlich das$\alpha \in W'$. Beweisen$W' \subseteq W$ Such dir irgendeine aus $\beta \in W'$ und beobachte das $f(\alpha)$ und $f(\beta)$ stimme dem ersten zu $n$Werte der Ausgabe. Dies impliziert das$f(\beta) \in V$ und daher $\beta \in W$, wie erforderlich.

Berechenbare Karten sind kontinuierlich als Karten zwischen algebraisch $\omega$CPOs

Lassen Sie mich zunächst feststellen, dass das, was Sie definiert haben, normalerweise "$\omega$CPO "($\omega$ im Namen gibt an, dass wir nur Suprema von Ketten benötigen).

In der Denotationssemantik entsprechen Datentypen $\omega$CPOs. Tatsächlich entsprechen sie der Algebra $\omega$CPOs (ist das in Ihrer Arbeit?), Die sind $\omega$CPOs, für die die kompakten Elemente eine Basis bilden. Hier sind einige Definitionen.

Definition: Let$D$ Bohne $\omega$CPO. Ein Element$d \in D$ist kompakt, wenn für jede Kette$x_0 \leq x_1 \leq \cdots$ so dass $d \leq \bigsqcup_i x_i$gibt es $j$ so dass $d \leq x_j$.

Definition: An$\omega$CPO ist algebraisch, wenn alle$x \in D$ ist das Supremum kompakter Elemente darunter.

Die Intuition hinter kompakten Elementen ist, dass sie "endliche Informationen" enthalten. Ein gutes Beispiel ist$\mathcal{P}(\mathbb{N})$, das Powerset der natürlichen Zahlen, geordnet nach $\subseteq$, wobei die kompakten Elemente genau die endlichen Teilmengen von sind $\mathbb{N}$(Übung!). Ein weiteres Beispiel: in der$\omega$CPO von kontinuierlichen Funktionen $\mathbb{N} \to \mathbb{N}_\bot$ Die kompakten Elemente sind die Teilfunktionen, die gleich sind $\bot$ überall, außer bei endlich vielen Argumenten.

Um zu sagen, dass ein $\omega$CPO ist algbraisch zu sagen, dass jedes Element vollständig durch die endlichen Informationen bestimmt wird, die es annähern. Es ist eine Tatsache, dass in der Denotationssemantik Datentypen der Algebra entsprechen$\omega$CPOs, es sei denn, wir machen etwas sehr Ungewöhnliches.

Wir können jetzt erklären, warum jede berechenbare Karte kontinuierlich ist. Annehmen$D$ und $E$ sind $\omega$CPOS und $f : D \to E$berechenbar. Annehmen$x \in D$, $e \in E$, $e$ ist kompakt und $e \leq f(x)$. Intuitiv sagt dies, dass "endliche Information$e$ erscheint in der Ausgabe $f(x)$". Weil $f$ ist berechenbar, muss es der Fall sein, dass es die Informationen berechnet hat $e$ durch Zugriff auf nur eine begrenzte Menge an Informationen über $x$dh es gibt einen kompakten $d \in D$ so dass $d \leq x$ und $e \leq f(d)$. Dieses Argument sollte mit dem obigen Argument der Turing-Maschine verglichen werden. Wir haben festgestellt:

Lemma: Wenn$f : D \to E$ ist berechenbar und $e \leq f(x)$ für einige $x \in D$ und ein kompakter $e \in E$, dann gibt es kompakt $d \in D$ so dass $d \leq x$ und $e \leq f(d)$.

Wir können das Lemma verwenden, um zu zeigen, dass es berechenbar ist $f$ist kontinuierlich. Annehmen$x_0 \leq x_1 \leq \cdots$ ist eine Kette in $D$. weil$f$ ist monoton, das wissen wir schon $\bigsqcup_i f(x_i) \leq f(\bigsqcup_i x_i)$, aber wir brauchen auch die Ungleichung $f(\bigsqcup_i x_i) \leq \bigsqcup_i f(x_i)$. weil$E$ ist algebraisch, es genügt zu zeigen, wann immer $e \in E$ ist kompakt und $e \leq f(\bigsqcup_i x_i)$ dann $e \leq \bigsqcup_i f(x_i)$. Also nimm an$e \leq f(\bigsqcup_i x_i)$. Durch das Lemma existiert ein Vertrag$d \in D$ so dass $d \leq \bigsqcup_i x_i$ und $e \leq f(d)$. weil$d$ ist kompakt, gibt es $j$ so dass $d \leq x_j$, daher durch Monotonie von $f$ wir haben $e \leq f(d) \leq f(x_j) \leq \bigsqcup_i f(x_i)$. Wir sind fertig.