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$?
Asked
Active
Viewed 116 times
1 Answers
0
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)$.
André Nicolas
- 507,029
-
The chapter containign this problem went over how primitive recursive functions are computable then gave a theory that composition of primitive computable functions are computable, so i assuemd that was my task. Can you explain more on how G1 and G2 are "inverses" and why do we want to find largest k such that 2^k divides z+1 for G1? – user270452 Sep 13 '15 at 19:32
-
They are inverses (sort of) of $G$ because using them we can recover $x$ and $y$ if we are given $G(x,y)$. As to the computation, maybe an example will help. What is $G(3,7)$? Compute. We get $2^3(15)-1$, that is, $119$. Now given $119$, how do we recover $x$? We kind of go backwards. Add $1$ to $119$. Now find the largest power of $2$ that divides $120$. This is $2^3$. So $120=2^3\cdot 15$. We want $x$ and $y$ such that $2^x=2^3$ and $2y+1=15$. Easily $x=3$ and $y=7$. – André Nicolas Sep 13 '15 at 19:52
-
Formally, $G_1$ and $G_2$ are defined by $G(x,y)=z$ if and only if $x=G_1(z)$ and $y=G_2(z)$. They are the functions that go backwards from the "answer" $z$ to the appropriate $x$ and $y$. Pairing functions such as $G$, and their associated unpairing functions $G_1$ and $G_2$ are very important in indexing (Goedel numbering). – André Nicolas Sep 13 '15 at 19:57
-
Thank you that makes a lot more sense now. – user270452 Sep 13 '15 at 20:13