User:IssaRice/Computability and logic/Function versus algorithm
In computability theory, a distinction is made between algorithms and functions.
Mapping between algorithms and computable partial functions
- Each algorithms computes exactly one function
- Each computable partial function has many different algorithms that compute it
Algorithm as index
If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as , for example, then actually we know more than just what the function is: we also know that is an integer that encodes the algorithm that computes . In contrast, if we just had some function called , then we know that some algorithm computes , but we have no name for it/a canonical choice for it, so we have to pick some number, say, , so that .