+-- {: .rightHandSide} +-- {: .toc .clickDown tabindex="0"} ### Context #### Constructivism, Realizability, Computability +-- {: .hide} [[!include constructivism - contents]] =-- =-- =-- #Contents# * table of contents {:toc} ## Idea A [[function]] is meant to be called _computable_ if its values on given input may be obtained by an actual [[computation]] (an [[algorithm]]). Making this precise and studying properties of computable functions is the topic of _[[computability theory]]_. There are two main concepts of computable functions, called "type I" and "type II": * In the type I case one considers functions operating on "finite strings of a finite alphabet" hence equivalently on the set of [[natural numbers]]. The computable functions in this case are _[[partial recursive functions]]_. * In the type II case one considers functions operating on "infinite strings of a finite alphabet" hence equivalently on the set of infinite sequences of [[natural numbers]] ("[[Baire space (computability)|Baire space]]"). The idea here is that the computation may be continued indefinitely to produce results always of finite but of ever increasing precision. Therefore this type II-concept is of relevance for computability in [[analysis]], hence in _[[computable analysis]]/[[constructive analysis]]_. See at _[[computable function (analysis)]]_. The following table summarizes this and related concepts: [[!include computable mathematics -- table]] ## References Lecture notes include * {#Bauer05} [[Andrej Bauer]], section 2 of _Realizability as connection between constructive and computable mathematics_, in T. Grubba, P. Hertling, H. Tsuiki, and [[Klaus Weihrauch]], (eds.) _CCA 2005 - Second International Conference on Computability and Complexity in Analysis_, August 25-29,2005, Kyoto, Japan, ser. Informatik Berichte, , vol. 326-7/2005. FernUniversität Hagen, Germany, 2005, pp. 378–379. ([pdf](http://math.andrej.com/data/c2c.pdf)) [[!redirects computable functions]]