Is there a phrase or word to describe an algorithim or program is complete in that given any value for its arguments there is a defined outcome?

Question

Is there a phrase or word to describe an algorithim or programme is complete in that given any value for its arguments there is a defined outcome? i.e. all the ramifications have been considered whatever the context?

A simple example would be the below function:

function returns string get_item_type(int type_no)
{
  if(type_no < 10)
    return "hockey stick"
  else if (type_no < 20)
    return "bulldozer"
  else
    return "unknown"
}

(excuse the dismal pseudo code)

No matter what number is supplied all possibiblites are catered for. My question is: is there a word to fill the blank here:

"get_item_type() is ______ complete"

?

(The answer is not Turing Complete - that is something quite different - but I annoyingly always think of something as "Turing Complete" when I am thinking of the above).

Answer 1

you could say it is a pure function

or if there is state to be considered besides the arguments you could say it is deterministic

Answer 2

Mathematically speaking, the term you are looking for is "Total Function" (a function that is defined for every possible value in some domain), as opposed to a "partial function", which is only defined for a subset of the possible input values.

Note that, strictly speaking, mathematical functions are always total on their own domain; calling a function "partial" only makes sense if you offset it against another domain, such as the function f(x) = 1/x: the domain of this function is the domain of all real numbers except zero, but against the domain of all real numbers (including zero), it is partial.

In programming, the types of a function's inputs state a domain already, and by not defining the function for all of them, you could say that the function is partial. However, many programming languages fall back to a default behavior when you don't explicitly return anything - they may return 0, null, undefined, etc. Technically speaking, such functions are still total - they return a value for all possible inputs -, but conceptually, there are gaps in the definition. And not all programming languages feature such fallbacks; the alternatives are refusing to compile, responding with "undefined behavior", raising an exception, etc.

BTW, note that neither determinism nor purity have anything to do with this. A deterministic function is one that always has the same effect given the same context (relevant system state and inputs); a pure function is a function that does not have any side effects (so that it always returns the same value given the same inputs, regardless of any outside state, and without influencing outside state in any way). You can easily come up with a function that is partial, yet fully deterministic (provided that partial functions are legal in your programming language, and definition gaps are handled in a predicatable way); and conversely, if you manage to write a non-deterministic function, e.g. by reading from a hardware entropy source, there is no reason why it would have to be total (nor partial). The same goes for purity, unless a definition gap automatically introduces side effects (then all pure functions must also be total).

Answer 3

In Your Case...

In your particular example, what we have is a pure surjective (partial) function.

_{(Don't be mislead by the "partial". See below.)}

---

To answer your question, we need to consider these:

Algorithms and Functions

Algorithms are implemented using either:

• a pure fuction (side-effects free), resulting in a deterministic algorithm (results are predictable and transposed to a mathematical function),
• or an impure function, resulting in a non-deterministic algorithm.

Functions

Functions can also considered as being either:

• a partial function (there's an output for all possible input),
• a total function (perfect input-output pairing).

Function Types

Furthermore, consider the following types of functions from a mathematical perspective:

An Injective Function

A partial function where results are unique.

A Surjective Function

A partial function where results can overlap.

A Bijective Function

A Total Function, both injective and surjective, where there's an output for all possible inputs, and where all possible outputs are distinct and obtained by a unique input, thus being perfectly paired.