# Difference between revisions of "User:IssaRice/Computability and logic/Function versus algorithm"

(→Algorithm as index) |
|||

Line 8: | Line 8: | ||

==Algorithm as index== | ==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 <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>. | + | 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 <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some computable partial function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>. |

## Revision as of 19:14, 4 February 2019

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 computable partial 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 .