This note will characterize those partial functions which are partial recursive under an arbitrary “renaming” of the integers.

The formal result. Let I be the non-negative integers. For any partial function f on I into I, and for any permutation σ of I, let fσ be the partial function which f becomes when the integers are renamed according to σ. That is, let fσ = σfσ−1 in the sense that fσ(x) is defined whenever σ−1(х) ∊ Dom f.