Linked from

The 15 pages that link to Computable function, each with the reason it gives.

• Church–Turing thesisBroader topic: The thesis equates effective calculability with computability in a formal model.

• Many-one reductionNarrower topic: The transforming map must be computable for the reduction to be effective.

• Constructive mathematicsRelated: Effective constructions often yield functions whose outputs can be computed.

• DecidabilityRelated: Deciders are computable procedures whose outputs encode yes or no.

• Universal Turing machineNarrower topic: Turing machines provide a formal model for computing such functions.

• DiagonalizationRelated: Computability limits are established by diagonalizing against proposed effective procedures.

• Deterministic algorithmRelated: A deterministic algorithm computes a function when its runs return the function’s values.

• Primitive recursive functionNarrower topic: Primitive recursive functions form a strict subclass of the total computable functions.

• Arithmetical hierarchyNarrower topic: Computable predicates provide the basic tests inside definitions at every level.

• ConstructivismRelated: Constructive existence often entails an effective procedure for finding the object claimed to exist.

• Kleene's recursion theoremNarrower topic: The theorem applies to effective transformations represented by computable operations on indices.

• Blum's speedup theoremNarrower topic: The theorem concerns programs computing one fixed computable function.

• CodeRelated: Computable translations between codes preserve effective information.

• S-m-n theoremNarrower topic: The theorem’s partial functions generalize this total, everywhere-defined case.

• Turing's proofRelated: A universal halting test would make the halting predicate computable.