Row Shuffling and Permutation Question

[SSequence]

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:
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₀ 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₁ 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.

 

[Baluncore]

I will attempt an answer by using an understanding of the single self indexed list.

Create a table of n indexes. Initialise each table entry to point to itself. Next, shuffle the table indexes into random order.

Select an initial entry in the table and follow that index to the next table entry, repeatedly.
At some point you will return to the entry where you started.
But you will not necessarily have visited all n entries. You may have been in a short tight loop.
The list will contain discrete cycles or rings of links with lengths of from 1 to n.

If it was a fair shuffle: The probability that there will be n links in one ring only is P₁ = 1 / n.
The probability that all entries will be self referential, that is n rings in the table is P_n = 1 / factorial( n ).
And surprisingly, the median number of rings found in the shuffled list will be the natural log of n.

 

[SSequence]

It seems that you are considering the case where there are finite number of rows (and the rows are of finite length).

Even in the case of infinite number of rows if the rows are of finite length, the answer to the question in the original post can be seen to be a yes (that is, a recursive P).

The "one dimensional" analogue to the question in the original post is to consider some recursive functions f:N→N and g:N→N. f is supposed to be a 1-1 function (but not necessarily onto). If you denote the image-set (the set f(N) that is) of f to be A, then we impose the condition that the image-set of g also has to be A (and furthermore g must also be 1-1). The question would then ask that whether for any arbitrary recursive function g whether the function P : N→N will always be recursive? (P would satisfy the equation f(x)=g(P(x)) for all values of x)
The answer in that case would also be yes.

In limited circumstances it is not difficult to see that the question to original answer is also yes. For example, if f is defined as:
f(x,y)=1 if y ≥ x
f(x,y)=0 if y < x
Then this is essentially the same problem as one-dimensional case.

But it isn't quite clear to me whether in general this should hold (and what would be the reason).

 

[SSequence]

I just wanted to say that if someone wants to post this on stackexchange etc. please feel free to do so (and also probably post back the link here). It would definitely be interesting to see a solution. The question in the original post is phrased precisely enough that there is no room for confusion (in any way).

I might have done it myself, but I don't have an account on that site. Perhaps sometime in future (but just for one question feels a bit strange I suppose).

 

[SlowThinker]

So we only have access to a blackbox implementing ##f##, and a blackbox implementing ##g##, and the task is to implement ##P##?
If both ##f## and ##g## take infinitely long inputs, I don't think it's possible to find the row of ##f## corresponding to a given row of ##g##, because you'd have to check all the rows.
For finite inputs, I'd say 2 nested for-loops should do the trick.

 

[SSequence]

So we only have access to a blackbox implementing ##f##, and a blackbox implementing ##g##, and the task is to implement ##P##?

f is ANY possible "total recursive function" which takes two variables as inputs (and hence is a function from N² to N). N is obviously natural numbers (including 0).
Only condition on f is that all of its rows are unique (no row occurs twice). I described that condition in a more formal way in post#1.

Now GIVEN a certain f, g is ANY possible total recursive function of two variables that re-arranges all the rows of f. That is:
(i) no row in g occurs twice either
(ii) the set of rows that occur in f and g are exactly the same

=====

What has to be determined is that given any possible combination of functions f and g (that satisfy the conditions above) can we show (essentially prove) P to be recursive? If not, then a counterexample should be given.

Edit: Also note that it is very easy to prove the following assertion:
If P is recursively bounded then P is recursive.

 

[SlowThinker]

I still don't understand how much information about ##g## we have.
The implementation of P has to look like this:

int P(int row)
 {
  for (int r=0; ; r++)
   {
    bool match=true;
    for (int c=0; ; c++)
      if F(r,c)!=G(row,c)
        { match=false; break; }
    if (match)
      return row;
   }
 }

This function will obviously be stuck at the inner loop once it finds the correct row, and will keep checking forever because there is no other way to know if it has found the correct row or not.
You could rearrange the function to loop through columns in the outer loop and rows in the inner loop but it will loop forever again, because we have infinite number of rows.

Tl;dr: your question does not make any sense.

 

[SSequence]

I still don't understand how much information about ##g## we have.

No more and no less than I mentioned in the previous post.

-----

What you are saying is that a single implementation of P in terms of f and g probably doesn't exist (but I think that has to be proved too). At any rate, if such an implementation existed it would certainly prove the required claim. However, even if it doesn't exist I don't see how it follows in an obvious manner that the required claim is false (and if it is false you have to show an example anyway).

To elaborate further on this, think of the following very simple example (already mentioned in post#3) as an illustration of the point I just made:

f is defined as:
f(x,y)=1 if y ≥ x
f(x,y)=0 if y < x

It is clear that f satisfies the required conditions. Now suppose that someone told you about a function g that satisfies the conditions I have already mentioned before. But the specific implementation of specific function g was completely hidden from you.
You could still easily write a function for P explicitly in that case (that would work regardless of g as long as it satisfied the required conditions). Of course that particular implementation of P would probably be likely to fail if f was a different function.

But it doesn't matter that much. The point isn't necessarily that whether we can write a single specific implementation of P in terms of f and g. The question is whether for any possible combinations of f and g (satisfying required conditions) does there exist some implementation of P or not.

I deduced some further facts that probably seem interesting enough. However, I don't know how much they contribute towards a direct solution. At any rate, I am not thinking about this problem further for now.p.s. This question might have been better suited for set theory/logic section I suppose (my reason for posting it here was that it belonged to ordinary recursion theory). Since this section would probably be more suited for questions that relate to programming/algorithms/time complexity questions etc.