function realizability


The subcategory on the effectively computable morphisms of the function realizability topos RT(𝒦 2)RT(\mathcal{K}_2) is the Kleene-Vesley topos KVKV. The category of “admissible representations” AdmRepAdmRep (whose morphisms are computable functions (analysis), see there) is a reflective subcategory of RT(𝒦 2)RT(\mathcal{K}_2) (BSS 07) and the restriction of that to KVKV is AdmRep effAdmRep_{eff}

AdmRep eff KV AdmRep RT(𝒦 2) \array{ AdmRep_{eff} &\hookrightarrow& KV \\ \downarrow && \downarrow \\ AdmRep &\hookrightarrow& RT(\mathcal{K}_2) }


type I computabilitytype II computability
typical domainnatural numbers \mathbb{N}Baire space of infinite sequences 𝔹= \mathbb{B} = \mathbb{N}^{\mathbb{N}}
computable functionspartial recursive functioncomputable function (analysis)
type of computable mathematicsrecursive mathematicscomputable analysis, Type Two Theory of Effectivity
type of realizabilitynumber realizabilityfunction realizability
partial combinatory algebraKleene's first partial combinatory algebraKleene's second partial combinatory algebra