Odwołanie do niezdefiniowanego modułu ciągłości funkcjonalnej w PCF?

Czy ktoś może wskazać mi odniesienie do niezdefiniowalności modułu ciągłości funkcjonalnej w PCF? \ newcommand {\ bool} {\ mathsf {bool}}$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\bool}{\mathsf{bool}}$

Andrej Bauer napisał bardzo fajny post na blogu , w którym szczegółowo omawia niektóre problemy, ale streszczę tylko trochę jego postu, aby nadać kontekst temu pytaniu. Baire'a przestrzeń jest zbiorem sekwencji liczb naturalnych lub równoważnie zbiór funkcji z Naturals do kasowniki . W przypadku tego pytania ograniczymy naszą uwagę tylko do strumieni, które są obliczalne.N → $B$$\N \to \N$

Teraz funkcja $f : B \to \bool$ jest ciągła, jeśli dla każdego $xs \in B$ wartość $f(xs)$ zależy tylko od skończonej liczby elementów $xs$ i jest obliczalna ciągła, jeśli faktycznie możemy obliczyć górną zależy od tego, ile elementów $xs$ jest potrzebnych. W niektórych modelach obliczeń faktycznie można napisać program $\mathsf{modulus} : (B \to \bool) \to B \to \N$ który przyjmuje funkcję obliczeniową w przestrzeni Baire i element przestrzeni Baire, i zwraca górną granicę liczby elementów strumienia.

Jednym ze sposobów na wdrożenie tego jest użycie pamięci lokalnej do zarejestrowania maksymalnego indeksu w widzianym strumieniu:

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

Oczywiście ysargument nie jest już programem czysto funkcjonalnym. Moje zainteresowanie tym programem wynika z faktu, że korzysta on tylko z lokalnego sklepu i dlatego jest wyjątkowo czysty. Pracuję nad (między innymi) programowaniem imperatywnym wyższego rzędu i projektuję teorie typów, które mogłyby zaklasyfikować to jako funkcję czystą.

Są też bardziej praktyczne przykłady, takie jak zapamiętywanie i łączenie połączeń, ale uważam to za szczególnie piękny przykład.

Dowód ukryty jest gdzieś w Troelstra i van Dalen, konstruktywizm w matematyce, tom 2, jak sądzę. Bardziej prawdopodobne jest, że można go znaleźć w dochodzeniach Troelstry , jeśli możesz położyć na nim ręce.

Tak to wygląda. Załóżmy, że możemy zdefiniować moduł ciągłości w typie -calculus za pomocą operatorów punktów stałych. Następnie moglibyśmy zinterpretować to w teoretycznym modelu domenowym, na przykład w gdzie jest modelem graficznym Scotta. W tym modelu obowiązuje zasada wyboru . Wiadomo jednak, że wraz z ekstensywnością funkcji (która obowiązuje w każdym modelu wykonalności) jest niezgodna z istnieniem modułu ciągłości. Jeśli mam chwilę, uzupełnię szczegóły później.P E R ( P ω ) P ω A C 2 , 0 A C 2 , $\lambda$$\mathsf{PER}(\mathcal{P}\omega)$$\mathcal{P}\omega$$AC_{2,0}$$AC_{2,0}$

Patrz także M. Escardo, T. Streicher: W dziedzinie realizacji domenowej nie wszystkie funkcjonały są ciągłe , opublikowane w Mathematical Logic Quarterly, tom 48, wydanie Suplement 1, strony 41-44, 2002 .