Re: [HM] base 5

Paul.Vitanyi@cwi.nl
Tue, 13 Apr 1999 14:39:59 +0200 (MET DST)

We used a complicated positional number system based on
-4,-3,-2,-1,0,1,2,3,4 in the paper [1]. The problem was
to devise a notation where one can maintain a count under
arbitrary unit increment (+1) and unit decrement (-1) and
check for zero (count = 0?) at every step, reading & updating only
the single symbol under scan and moving one symbol left or right
at every step. The movement should be oblivious, that is, the
movement at step t is a fixed function m(t) \in \{ left, right\}.
(We wanted to simulate a counter machine in real-time by a turing machine
with one work tape). The solution to this (at the time long-standing
open) problem involves a complicated positional notation with remarkable
properties: Every i-th position is updated according to the `binary carry
schedule':

\noindent These requirements are met, for example, by a schedule that
provides a $0$-opportunity every other step, a $1$-opportunity every
other remaining step, a $2$-opportunity every other still remaining
step, etc.:
$$0\,1\,0\,2\,0\,1\,0\,3\,0\,1\,0\,2\,0\,1\,0\,4\,
0\,1\,0\,2\,0\,1\,0\,3\,0\,1\,0\,2\,0\,1\,0\,5\,
0\,1\,0\,2\,0\,1\,0\,3\,0\,1\,0\,2\,0\,1\,0\,4\,
0\,1\,0\,2\ldots\,{}.$$
This is the sequence of carry propagation distances when we count in
binary, so let us call it the {\demph binary carry schedule}.

The useful aspect
of such a notation is that one can delay propagating carries
and borrows so that every position is always handled "just in time.".

[1] J. Seiferas and P.M.B. Vitányi, Counting is easy,
J. Assoc. Comp. Mach., 35 (1988), pp. 985-1000.
downloadable from http://www.cwi.nl/~paulv/complexity.html