Show that $G$ is a computable bijection and that the functions $G(G_1(z))$,$G_2(z))=z$ for all $z$ is computable. To show that it is computable, do we show that the above function $G$ is primitive recursive? I don't understand the second equation either and how we get $z$?
2026-04-01 00:56:37.1775004997
Let $G(x,y)=2^x(2y+1)-1$ and show that $G$ is computable
117 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
The level of formality at which you are expected to operate is course-dependent. However, the use of the term "computable" indicates to me that you are not expected to show in detail that the function $G$ is recursive. The function $G$ is in fact primitive recursive, and primitive recursive of a very simple type.
Possibly you are just expected to note there is an obvious algorithm for computing $G(x,y)$.
The function $G$ is a one to one mapping of the set of ordered pairs $(x,y)$ of non-negative integers to the set of non-negative integers. It is one example of a pairing function.
As to the two "inverse" functions $G_1$ and $G_2$, they are used to recover $x$ and $y$ if we are given $G(x,y)$.
Suppose that $G(x,y)=z$. Given $z$, we recover $x$ as follows. We add $1$ to $z$. Then we find, possibly by repeated division by $2$, the largest $k$ such that $2^k$ divides $z+1$. One can certainly write a computer program that does that. So $G_1(z)$ is a computable function of $z$. To find $G_2(z)$ is also not hard. We divided $z+1$ by $2$ until we could not do it any more. The odd quotient we are left with is $2y+1$, from which we can easily recover $y$, that is, $G_2(z)$.