PROBLEM: register swap                  Torsten Sillke, 28.12.95
----------------------

An old (progamming) teaser is:

  Exchange two registers a and b without further memory.

As everybody knows, this can be done by three XORs.

'Dr. Ecco' asked for a cyclic permutation of 7 registers.

So consider the general case:

  GL_n (F_2) is generated by the I + E_i,j (with i <> j).
  The E_i,j are the elementary matrices. Only one entry is
  not zero: the (i,j) one.

  What is the diameter of the Cayley graph?

  The information theoretic bound is C*n*n/log(n).
  Gaussian elimination needs at most n*n steps.

Conjecture:
  Permutation matrices need 3*t generators.
  t: minimal number of transpositions to generate the permutation.

  (I verified this by computation for n <= 5.)
  For n <= 5 the diameter is 3(n-1).

If this is true, the n-register cyclic shift is no good puzzle,
as it reduces to the 2-register one.
---------------------------------------------------------
EXC: Exchange (Register Swap without tmp-memory)
EXC- Dennis Shasha, Codes, Puzzles, and Conspiracy, Freeman (1992), Ex. 37
EXC   exchange 2 registers, cyclic permute 7 registers (without minimal. proof)
EXC- Peter van der Linden, Expert C Programming - Deep C Secrets, 
EXC   Prenctice Hall (SunSoft Press) (1994), p 287-289 
EXC   The Limitations of Program Proofs
EXC- sio:  S_n is a subgroup of GL(n,F2).
EXC    S_n is generated by transpositions, GL(n,F2) is generated by 'exoring'.
EXC    Elementary Matrices E_i,j :  E_i,j(n,m) = (n == i)(m == j)
EXC                        I_i,j := I + E_i,j   with i != j.
EXC    Generate GL(n,F2) = < {I_i,j | i != j} >
EXC    Problem: Is  #transpositions = 3*#exorings for permutaion-matrices?
EXC    Problem: How long is a worst case minimal representation?
EXC             Infomation theoretic bound is: c * n^2 / log(n)
EXC             trivial upper bound (gauss elimination): n^2
EXC- Kiltinen, How few transpositions suffice? ... you already know
EXC   M. Mag. 67:1 (Feb 1994) 
EXC- Letter: M. Mag. 68:1 (Feb 1995) 79  (How few transpositions suffice?)
EXC- Jacobson, Lectures in Abstract Algebra I (1951) p 36 (transpositions)
EXC- Sury, An Integral Polynomial, M. Mag. 68:2 (Apr 1995) 134-135
EXC   Let a1 < a2 < ... < a(n) integers
EXC   Product_(i>j) (a(i) - a(j))/(i - j) is an integer.
EXC   Product_(i>j) (x^(a(i)-a(j)) - 1)/(x^(i-j) - 1) is an integral polynom.
---------------------------------------------------------
Most of the generators in the xor-problem above commute.
So we lock for a good lower bound for the diameter of such graphs.

Let G be a regular and vertex-transitive Graph.
  Gamma(x) : Set of all vertices adjacent to x.
  v  : Number of vertices of G.
  d  = #Gamma(x)  for all x.                  (vertices of distant 1)
  d2 = #( Gamma(Gamma(x)) / Gamma(x) / {x} )  (vertices of distant 2)

  diam(G) >= F(v, d, d2)

What functions F are known?
---------------------------------------------------------
==== Reversable-Computations ====

From: hbaker@netcom.com (Henry G. Baker)
Subject: Re: register swap

> Torsten Sillke:
>     An old (progamming) teaser is:
>       Exchange two register a and b without further memory.
>     As everybody know, this can be done by XOR three times.
> 
> Gosper once pointed out an interesting exception to this rule:
> 
> If the two registers are actually the same register (not just
> equal contents, but the same register), the triple xor fails.

An interesting insight into this problem is the fact that swap is
_reversible_ unless one swaps with a descendant of one of the
registers (including the 0'th order descendant -- one's self!).

swap a,a kills a, of course!  swap a,cddr(a) can create a cyclic list
which becomes disconnected from the rest of the world (i.e., garbage).

As Knuth V.I shows, many interesting list processing operations
(including 99% of Deutsch-Schorre-Waite GC) can be performed using
only swaps.  Gosper continues this in hakmem.  Suzuki CACM 1982 shows
the general case.

My 1992 paper "NREVERSAL of Fortune" utilizes swapping (and other
invertible operations) to construct a reversable computer which
doesn't require Prolog-like or database-like storage of intermediate
values.

(ftp://ftp.netcom.com/pub/hb/hbaker/ReverseGC.html and .ps.Z)

The pointer to the Suzuki reference is in my paper.

-- 
Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html