A partial function is like a function , but where we relax the requirement that must be defined for all . That is, it must still be the case that " and is defined" implies " is defined and ", but now we no longer need to be defined everywhere. We can write [1]to denote that is a partial function with domain and codomain : that is, whenever is defined then we have and .
This idea is essentially the "flip side" to the distinction between the codomain vs image dichotomy.
Just as a function can be implemented as a set of ordered pairs such that:
so we can define a partial function as a set of ordered pairs such that:
(That is, we omit the first listed requirement from the definition of a bona fide function.)
Morally speaking, every Turing machine may be viewed as computing some function , by defining to be the state of the tape after has been allowed to execute on the tape which has been initialised with the value .
However, if does not terminate on input (for example, it may be the machine "if then return ; otherwise loop indefinitely"), then this "morally correct" state of affairs is not accurate: how should we define ? The answer is that we should instead view as a partial function which is just undefined if fails to halt on the input in question. So with the example above, is the partial function which is only defined at , and .
In LaTeX, this symbol is given by \rightharpoonup
.