Function composition in computability

Question

I have been reading Cutland's computability book, which is really good! However, I have found myself thinking way too much about one little passage in the the third section of the second chapter (the second chapter is on generating computable functions, and the third section in this chapter is on substitution/composition). Cutland says that "New functions can be obtained from any given function by rearranging or identifying its variables, or by adding new dummy variables." He goes on to say that "for instance from a function $f(y_1, y_2)$ we can obtain" the functions

• $h_1(x_1, x_2) \cong f(x_2, x_1)$, rearrangement
• $h_2(x) \cong f(x, x)$, identification
• $h_3(x_1, x_2, x_3) \cong f(x_2, x_3)$, adding dummy variables.

In what sense are these $h$'s new functions? The way I understand it, he is saying that given a computable function $f$, a function $h$ that merely alters the form of $f$'s variable inputs is computable as well. Take rearrangement, for example. Let $U^{n}_i$ be the projection function that maps an $n$-tuple to its $i$-th coordinate (a computable function). If $f(x_2, x_1)$ is the addition function, then one sees that if $h$ is defined $h(x_1, x_2) = f(U^{2}_2, U^{2}_1)$, then $h$ is computable, since $f$ and $U^{n}_i$ are computable. Is this what Cutland has in mind when he mentions rearrangement? Am I understanding this correctly? Thanks.

Addendum: Sorry for squeezing in this last question, but what is meant by "identification"?

Answer 1

Yes, you're right. Usually, we use $$\pi_n^k(x_1,x_2,\dots,x_n)=x_k$$

And then, by composition:

1. $h(x,y)=f\left(\pi_2^2(x,y),\pi_2^1(x,y)\right)=f(y,x)$
2. $h(x)=f\left(\pi_1^1(x),\pi_1^1(x)\right)=f(x,x)$
3. $h(x,y,z)=f\left(\pi_3^1(x,y,z),\pi_3^2(x,y,z)\right)=f(x,y)$

And by identification, from $f(x,y)$ you identify $x$ to $y$ (you say that those two names $x$ and $y$ are the same variable), to obtain $f(x,x)$.