The question below could also be re-phrased in terms of functions of one variable (using indexes). However, it seems it is easier to explain it with two variables. Here is the question:(adsbygoogle = window.adsbygoogle || []).push({});

Suppose we have some total recursive function f: N x N→N. Define the n-th row of f as the function F_{n}: N→N where:

F_{n}(x) = f(x,n)

Now suppose that every single row of the function f is unique. What that means precisely is that for any two distinct row numbers a and b (where a≠b) we have F_{a}≠F_{b}.

Consider an arbitrary total recursive function g: N x N→N (not given in advance). It is given that the function g "shuffles" the rows of the function f (without changing any of them). Therefore every single row of the function g is also unique (and the set of rows that occur in functions f and g are the same).

Now given the above there must be a unique permutation function P : N→N such that when it is applied to a given row number of f gives us the position of occurrence of the same row in function g. For example, if some function F_{0}occurred as the 0-th row in the function f, and the same function occurred as the 20-th row in function g, we have P(0)=20. If some function F_{1}occurred as 1st row in function f, and the same function occurred as 0-th row in function g, we have P(1)=0.

The question asks that whether the function P is always recursive or not? If it is, then it has to be shown why and if it isn't then at least one counterexample has to be given (by specifying some specific functions f and g).

P.S. The question could be shifted to some other sub-section if it seems appropriate. I wasn't sure myself which was the most appropriate sub-section for this question.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Row Shuffling and Permutation Question

Have something to add?

Draft saved
Draft deleted

Loading...

Similar Threads for Shuffling Permutation Question |
---|

C/++/# Question about running "executables" without source code |

Big-O Notation Question |

C/++/# Question about input format file (for creating a net) |

Latex article template question |

Python Shuffling in classification problems |

**Physics Forums | Science Articles, Homework Help, Discussion**