nLab
Type Two Theory of Effectivity

Context

Analysis

Constructivism, Realizability, Computability

Contents

Idea

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.

computability

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

References

The original article is

The equivalence of this to real PCF is shown in

See also