Polynomial Time Computable Structures

[Vaughan Pratt]

The day after I posted my P1-effective (i.e. linear time in both
directions) GoedeI numbering of the rationals in (0,1) I dropped in on Don
Knuth to ask what he knew about all this.  He pointed me to the
Stern-Brocot tree, a binary tree which extends the Farey sequence of
rationals in (0,1) to the positive rationals, essentially by pairing the
rationals in (0,1) with their reciprocals in (1,oo) and making 1 their
common root.  It was defined independently in 1858 by Moritz Brocot, a
German number theorist, and in 1861 by Achille Brocot, a French clockmaker.

It occurred to me that a further pairing of the positive rationals with the
negative rationals would extend the Stern-Brocot tree to a similar
bijection between the set N+ of positive integers and the set Q of all
rationals, itself forming a binary tree with 0 at the root.  Absent a
source for this I'll call it the Augmented Stern-Brocot tree or ASB tree.

Defining the ASB sequence to be a breadth-first left-to-right enumeration
of the nodes of the ASB tree, the sequence is 0 at level 0;  -1 and 1 at
level 1;  -2, -1/2, 1/2, and 2 at level 2;  -3, -3/2, -2/3, -1/3, 1/3, 2/3,
3/2, and 3 at level 3; and so on.  The corresponding Goedel numbers in
binary are 1 at level 1, 10 and 11 at level 2, 100, 101, 110, and 111 at
level 3, 1000 through 1111 at level 4, and so on.  The level gives the
number of bits following the leading 1 of the Goedel number when written
binary.

The ASB tree furnishes Q with a natural division into eight octants as
follows.  Zero splits Q into halves Q0 and Q1, respectively the negative
and positive rationals.  Then 1 splits Q1 into quadrants Q10 and Q11,
respectively (0,1) and (1,oo) (and -1 splits Q0 similarly).  Finally 2
splits the quadrant Q11 (in which n > d) into octants Q110 and Q111
according to whether n - d is smaller or greater than d respectively (and
similarly for the splitters -2, -1/2, and 1/2).

The first four bits of a rational's Goedel number determine the octant it
belongs to.

Let m(n/d) = -n/d (minus), r(n/d) = d/n (reciprocal), and h(n/d) = n/(n-d)
be three involutions defined on Q, Q1, and Q11 respectively.  Note that all
three have their domain's splitter (root) as their unique fixpoint,
respectively 0, 1, and 2, and below their root they mirror the two subtrees
in each other.  Further define k: Q111 --> Q11 as k(n/d) = (n+d)/d having
k'(n/d) = (n-d)/d as its inverse.

We can now define a function g: Q  ->  N+ giving the Goedel number g(n/d)
for each rational n/d in Q.  We start by defining its inverse g': N+ --> Q
recursively as follows with the help of bijections h,k: Q11 -> Q11
satisfying h(n/d) = n/(n-d) and k(n/d) = (n+d)/d, bearing in mind that in
Q11, n > d.  Only h is an involution, the inverse of k satisfies k'(n/d) =
(n-d)/d.

In the following recursive definition we assume Goedel numbers are passed
to g' in binary, and we write the bitwise complement of the bit string w as
W.

1. g'(1^n) = (n-1)/1 for n < 4.  (Rule 5 caters for larger n)
2. g'(10w)  =  m(g'(11W))         (obtains Q0 from Q1)
3. g'(110w)  =  r(g'(111W))       (obtains Q10 from Q11)
4. g'(1110w)  =  h(g'(1111W))   (obtains Q110 from Q111)
5. g'(1111w) =  k(g'(111w))       (obtains Q111 from a lower level in Q11)

Rules 2-4 are antimonotone; 5 is monotone (w instead of W).

The inverse g of g', mapping n/d to its Goedel number in binary, can be
computed iteratively as follows by outputting a bit at a time and applying
m, r, h, or k' (where  k'(n/d) = (n-d)/d is the inverse of k) to n/d as
specified.

The commands MC, RC, and HC apply m, r, or h respectively to n/d and then
complements t (i.e. t := 1 - t).

The command T appends the current value of t (0 or 1) to the output.  The
command KT applies k' to n/d and then does T.

c?a and c?a:b are conditionals, respectively without and with an else part
:b.

t := 1;
T
n/d = 0/1? halt
n/d < 0? MC
T
n/d = 1/1? halt
n < d? RC
T
while n/d != 2/1
   n-d < d? HC: KT

In my previous email I'd written both directions recursively.  However I
felt my recursive implementation of g was rather clumsy, and found it more
natural to implement g iteratively as above.  Has anyone else run across
this phenomenon when inverting a recursive definition, namely easier to
write iteratively?

For a bijection with the set N of natural numbers, compose g' with the
successor function s:N -> N+, another P1-effective bijection.  Thus
g'(s(0)) = 0/1, g'(s(1)) = -1/1, etc.

Vaughan Pratt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211217/abdcc15a/attachment.html>