Total function

From Esolang
(Redirected from Partial function)
Jump to navigation Jump to search

A total function is a function which is defined for all inputs, that is, no input to the function will ever result in the answer undefined. In the context of computer science, machines which halt (or equivalent definitions) on a given input are considered to have a defined output. Machines which do not halt on a given input are considered to have an undefined output. Therefore, a machine which halts on all inputs is total since it models a total function of its input.

Functions which are not defined for all inputs are called partial functions. Since the only computable method to determine membership in recursively enumerable (computable) sets is by using a Turing machine (or equivalent model) which has the ability to loop indefinitely, only partial functions are able to model membership in these sets. Meaning that total functions are inherently less capable than partial functions.

Since total machines can never loop indefinitely, they can be considered to be more practical and useful than partial machines, since it's guaranteed that there will be an answer at some point. Programming languages which require and enforce that all valid programs are total are called total languages. Since total functions cannot model all computable sets, these languages are not Turing complete.

See also