computable function



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”:

The following table summarizes this and related concepts:


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


Lecture notes include