Type Two Theory of Effectivity



Constructivism, Realizability, Computability



What is called Weihrauch’s Type-2 Theory (Weihrauch 87) is a measure for the complexity of computable functions on non-discrete topological spaces such as the real line, the topic of computable analysis. While some approaches to computability of continuous functions take pointwise addition as an elementary operation, Weihrauch’s Type-2 theory is instead “bit oriented” and takes into account the finitary aspects of computation.

A quick survey is in the beginning of (Schröder 04).

Essentially the type-II theory considers functions between topological spaces which may be encoded by infinite sequences of natural numbers, this is discussed in detail at computable function (analysis). As such this is a mathematical theory of computability closely related to exact real computer arithmetic.


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


The original article is

The equivalence of this to real PCF is shown in

See also