since each turing program is a finite set of quintuples, we can list all turing programs in such a way that for any program we can effectively find its number on the list, and conversely. using godel numbering.
- let be the turing program with code number in this coding, also called the godel number or index .
- let be the partial function of variables computed by . let denote . we call a partial computable function. we identify the turing program and p.c. function with index .
this is called the standard numbering or canonical numbering of turing program and partial computable functions. any other effective numbering will be computably isomorphic to this one.
the second method uses the standard pairing function and has the added advantage that the -tuple coding is an injective and surjective map from onto .