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

10

Kann mich jemand auf die Referenz für die Nichtdefinierbarkeit des in PCF funktionalen Kontinuitätsmoduls hinweisen? \ 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 NN . Bei dieser Frage beschränken wir uns nur auf die berechenbaren Streams.

Nun ist eine Funktion f:Bbool stetig, wenn für jedes xsB 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,modulus:(Bbool)BN 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.

Neel Krishnaswami
quelle

Antworten:

4

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.λPER(Pω)PωAC2,0AC2,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 .

Andrej Bauer
quelle
Ich habe es nachgeschlagen. Es ist in Troelstra und van Dalens "Konstruktivismus in der Mathematik, Band 2", Abschnitt 6.10, Seite 500. Ich denke, ich werde dies in meinem Blog veröffentlichen, weil es furchtbar schwer zu finden ist.
Andrej Bauer
Vielen Dank! Was ist das Axiom? AC2,0
Neel Krishnaswami
( x X y Y . R ( x , y ) ) , f Y Xx X . R ( x , f ( x ) ) A C 2 , 0 A C ( N N N , N )AC(X,Y) ist , und dann ist . (xXyY.R(x,y))fYXxX.R(x,f(x))AC2,0AC(NNN,N)
Andrej Bauer
Ok, hier ist die Hälfte des Beweises: math.andrej.com/2011/07/27/…
Andrej Bauer