Referenz für die Undefinierbarkeit des Kontinuitätsmoduls in PCF?

Kann mich jemand auf die Referenz für die Nichtdefinierbarkeit des in PCF funktionalen Kontinuitätsmoduls hinweisen? \ newcommand {\ bool} {\ mathsf {bool}}$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\bool}{\mathsf{bool}}$

Andrej Bauer hat einen sehr schönen Blog-Beitrag geschrieben , in dem einige der Themen ausführlicher behandelt werden. Ich werde jedoch nur einen kleinen Teil seines Beitrags zusammenfassen, um dieser Frage einen Kontext zu verleihen. Der Baireschen Raum $B$ ist die Menge der natürlichen Zahlenfolgen, oder in äquivalenter Weise die Menge der Funktionen von naturals zu naturals $\N \to \N$ . Bei dieser Frage beschränken wir uns nur auf die berechenbaren Streams.

Nun ist eine Funktion $f : B \to \bool$ stetig, wenn für jedes $xs \in B$ der Wert von $f(xs)$ nur von einer endlichen Anzahl der Elemente von xs abhängt $xs$, und es ist rechnerisch stetig, wenn wir tatsächlich ein Oberes berechnen können gebunden, wie viele Elemente von $xs$ benötigt werden. In einigen Berechnungsmodellen ist es tatsächlich möglich, ein Programm \ mathsf {modulus} zu schreiben : (B \ to \ bool) \ to B \ to \ N,$\mathsf{modulus} : (B \to \bool) \to B \to \N$ das eine berechenbare Funktion für den Baire-Raum und ein Element des Baire-Raums übernimmt. und gibt die Obergrenze für die Anzahl der Elemente des Streams zurück.

Ein Trick, um dies zu implementieren, besteht darin, lokalen Speicher zu verwenden, um den maximalen Index im angezeigten Stream aufzuzeichnen:

let modulus f xs =
  let r = ref 0 in
  let ys = fun i -> (r := max i !r; xs i) in 
    f ys;
    !r

Natürlich ist das ysArgument kein rein funktionales Programm mehr. Mein Interesse an diesem Programm kommt von der Tatsache, dass es nur lokale Geschäfte nutzt und daher weitgehend rein ist. Ich arbeite (unter anderem) an imperativer Programmierung höherer Ordnung und entwerfe Typentheorien, die dies als reine Funktion klassifizieren könnten.

Es gibt auch praktischere Beispiele, die Dinge wie Memoisierung und Verbindungspooling beinhalten, aber ich finde dies ein besonders schönes Beispiel.

Der Beweis ist irgendwo in Troelstra und van Dalen versteckt, Konstruktivismus in der Mathematik, Band 2, nehme ich an. Wahrscheinlicher ist es in Troelstras Ermittlungen zu finden , wenn Sie Ihre Hände darauf legen können.

Es geht so. Angenommen, wir könnten den Kontinuitätsmodul in typisiertem Kalkül mit Fixpunktoperatoren definieren. Dann könnten wir es in einem domänen-theoretischen Realisierbarkeitsmodell interpretieren, zum Beispiel in wobei Scotts ist. In diesem Modell gilt das . Es ist jedoch bekannt, dass zusammen mit der Erweiterbarkeit von Funktionen (die in jedem Realisierbarkeitsmodell gilt) nicht mit der Existenz eines Kontinuitätsmoduls kompatibel ist. Wenn ich einen Moment Zeit habe, werde ich die Details später ausfüllen.$\lambda$$\mathsf{PER}(\mathcal{P}\omega)$$\mathcal{P}\omega$$AC_{2,0}$$AC_{2,0}$

Siehe auch M. Escardo, T. Streicher: In Bezug auf die Realisierbarkeit von Domänen sind nicht alle Funktionen kontinuierlich , veröffentlicht in Mathematical Logic Quarterly, Band 48, Ausgabe Supplement 1, Seiten 41-44, 2002 .