Real number computation through gray code embedding.
We propose an embedding G of the unit open interval to the set {0, 1},1 of infinite sequences of {0, 1} with at most one undefined element. This embedding is based on Gray code and it is a topological embedding with a natural topology on {0, 1},1. We also define a machine called an indeterministic multihead Type 2 machine which input/output sequences in {0, 1},1, and show that the computability notion induced on real functions through the embedding G is equivalent to the one induced by the signed digit representation and Type 2 machines. We also show that basic algorithms can be expressed naturally with respect to this embedding.
Introduction
One of the ways of dening computability of a real function is by representing a real
number x as an innite sequence called a name of x, and dening the computability
of a function by the existence of a machine, called a Type-2 machine, which inputs
and outputs the names one-way from left to right. This notion of computability dates
back to Turing[Tur36], and is the basis of eective analysis [Wei85,Wei00].
This notion of computability depends on the choice of representation we use, and
signed digit representation and equivalent ones such as the Cauchy representation
and the shrinking interval representation are most commonly used; they have the
property that every arbitrarily small rational interval including x can be obtained
from a nite prex of a name of x, and therefore induces computability notion that
a function f is computable if there is a machine which can output arbitrary good
approximation information of f(x) as a rational interval when arbitrary good approximation
information of x as a rational interval is given. The naturality of this
computability notion is also justied by the fact that it coincides with those de-
Preprint submitted to Elsevier Science 15 June 2000
ned through many other approaches such as Grzegorczyk's ([Grz57]), Pour-El and
Richards ([PER89]), and domain theoretic approaches([ES98], [Gia99]).
One of the properties of these representations is that they are not injective [Wei00].
More precisely, uncountably many real numbers have innitely many names with
respect to representations equivalent to the signed digit representation [BH00]. This
kind of redundancy is considered essential in many approaches to exact real arithmetic
[BCRO86,EP97,Gia96,Gia97,Vui90].
Thus, computability of a real function is dened in two steps: rst the computability
of functions over innite sequences is dened using Type-2 machines, and then it is
connected with the computability of real functions by representations. The redundancy
of representations means that we cannot dene the computability of a real
function more directly by considering an embedding of real numbers into the set of
innite sequences on which a Type-2 machine operates. In this paper, we consider
such a direct denition by extending the notion of innite sequences and modifying
the notion of computation on innite sequences.
Our embedding, called the Gray code embedding, is based on the Gray code expan-
sion, which is another binary expansion of real numbers. The target of this embedding
is the set f0; 1g !
?;1 of innite sequences of f0; 1g in which at most one ?, which means
undenedness, is allowed. We dene the embbeding G of the unit open interval I,
and then explain how it can be extended to the whole real line in the nal section.
?;1 has a natural topological structure as a subspace of f0; . We show
that G is a topological embedding from I to the space f0; 1g !
?;1 .
Because of the existence of ?, a machine cannot have sequential access to inputs
and outputs. However, because ? appears only at most once, we can deal with it by
putting two heads on a tape and by allowing indeterministic behavior to a machine.
We call such a machine Indeterministic Multihead Type 2 machine (IM2-machine for
short). Here, indeterministic computation means that there are many computational
paths which will produce valid results [She75,Bra98]. Thus, we dene computation
over
using IM2-machines, and consider the induced computational notion on
I through the embedding G. We show that this computational notion is equivalent
to the one induced by the signed digit representation and Type-2 machines.
We also show how basic algorithms like addition can be expressed with this represen-
tation. One remarkable thing about this representation is that it has three recursive
structures though it is characterized by two recursive equations. This fact is used in
composing basic recursive algorithms.
We introduce Gray code embedding in Section 2 and an IM2 machine in Section 3.
Then, we dene the Gray code computability of real functions in Section 4, and show
that it is equivalent to the computability induced by the signed digit representation
and Type 2 machines in Section 5. In Section 6, we study topological structure.
number Binary code Gray code
9 1001 1101
Fig. 1. Binary code and Gray code of integers
In Section 7 and 8, we consider basic algorithms with respect to this embedding.
We will discuss how this embedding can be extended to R, give some experimental
implementations, and give conclusion in Section 9.
Notation: Let  be an alphabet which does not include ?. We write   for the set of
nite sequences of ,  ! for the set of innite sequences of , and  !
for the set of innite sequences of  in which at most n instances of the undenedness
character ? are allowed to exist. We
from X to Y , and multi-valued function from X to Y , that
is, F is a subset of X  Y considered as a partial function from X to the power set
of Y . We call a number of the form m 2 n for integers m and n a dyadic number.
Gray Code Embedding
Gray code is another binary encoding of natural numbers. Figure 1 shows the usual
binary code and the Gray code of integers from 0 to 15. In this way, n-bit Gray code
is composed by putting the n-th bit on and reversing the order of the coding up to (n-
1)-bits, instead of repeating the coding up to (n-1)-bits as we do in the usual binary
code. The importance of this code lies in the fact that only one bit diers between
the encoding of a number and that of its successor. This code is used in many areas
of computer science such as image compression [ASD90] and nding minimal digital
circuits [Dew93].
The conversion between these two encodings is easy. Gray code is obtained from the
usual binary code by taking the bitwise xor of the sequence and its one-bit shift.
Therefore, the function to convert from binary code to Gray code is written using
the notation of a functional language Haskell [HJ92] as follows:
This conv function has type [Int] -> [Int], where [Int] is the Haskell type of
(possibly innite) list of integers. a:b means the list composed of a as the head and
b as the tail, xor is the \exclusive or" dened as
xor (0,
xor (0,
xor (1,
xor (1,
and zip is a function taking two lists (of length l and m) and returning a list of pairs
(of length min(l; m)). This conversion is injective and the inverse is written as
with [] the empty list.
We will extend this coding to real numbers. Since the function conv is applicable to
innite lists, we can obtain the Gray code expansion of a real number x by applying
conv to the binary expansion of x.
The Gray code expansion of real numbers in the unit interval I = (0; 1) is visualized
in

Figure

2. Here, a horizontal line means that the corresponding bit has value 1
on the line and value 0 otherwise. This gure has a ne fractal structure and shows
symmetricity of bits greater than n at every dyadic number m 2 n .
bit3
bit6Fig. 2. Gray code of real numbers
In the usual binary expansion, we have two expansions for dyadic numbers. For
example, can be expressed as 0:110000::: and also as 0:101111:::. This is also the
case for the Gray code expansion. For example, by applying conv to these sequences,
we have the two sequences 0:101000::: and 0:111000::: of However, one can nd
that the two sequences dier only at one bit (in this case, the 2nd). This means that
the information that this number is only by the remaining bits and the
2nd bit does not contribute to this fact. Therefore, it would be natural to introduce
the character ? denoting undenedness and consider the sequence 0:1?1000::: as the
unique representation of Note that the sequence after the bit where they dier
is always 1000:::. Thus, we dene Gray code embedding of I as a modication of
the Gray code expansion in that a dyadic number is represented as s?1000::: with
Denition 1 The Gray code embedding of the unit open interval I is an injective
function G from I to  !
?;1 which maps x to an innite sequence a 0 a
as follows: a for an odd number m,
a if the same holds for an even number m, and a
for some integer m. We call G(x) the modied Gray code expansion of x, or simply
Gray code of x.
When or 0, according as x is bigger than, equal to, or less
. The tail function which maps x to G 1 (a 1 a denotes the so-called tent
It is in contrast to the binary expansion in that the tail function of the binary
expansion denotes the function
Note that Gray code expansion coincides with the itinerary by the tent map which
is essential for symbolic dynamical systems [HY84].
3 Indeterministic Multihead Type 2 Machine
Consider calculating a real number x (0 < x < 1) as the limit of approximations and
output the result as the modied Gray code expansion. More precisely, we consider a
calculation which produces shrinking intervals (r successively so
that lim n!1 s
When we know that x < n), we can write 0 as the rst digit.
And when we know that n), we can write 1. However,
when neither will happen and we cannot ever write the rst digit. Even so,
when we know that we can skip the rst and write 1 as the second digit,
and when we know that as the third digit. Thus, when
, we can continue producing the digits skipping the rst one and we can write
the sequence from the second digit. In order to produce the Gray code of
x as the result, we need to ll the rst cell with ?, which is impossible because we
cannot obtain the information in a nite time. To solve this, we dene ? as
the \blank character" of the output tape and consider that the output tape is lled
with ? at the beginning. Thus, when a cell is skipped and is not lled eternally, it is
left as ?.
Suppose that we know we have written the second digit as 1 skipping
the rst one. As the next output, we have two possibilities: to write the third digit
as 0 because we know that or to write the rst digit because we obtain
the information x < Therefore, when we consider a machine with Gray
code output, the output tape is not written one-way from left to right. To present
this behavior in a simple way, we consider two one-way heads H 1 (O) and H 2 (O) on an
output tape O which move automatically after an output. At the beginning, H 1 (O)
and H 2 (O) are located above the rst and the second cell, respectively. After an output
from H 2 (O), H 2 (O) is moved to the next cell, and after an output from H 1 (O), H 1 (O)
is moved to the position of H 2 (O) and H 2 (O) is moved to the next cell. Thus, in order
to ll the output tape as
Here, H(j) (H is H 1 (O) or H 2 (O) and means to output j from H . With this
head movement rule, each cell is lled at most once and a cell is not lled eternally
only when H 1 (O) is located on that cell and output is made solely from H 2 (O).
are on the s-th and t-th cell of an output tape, the i-th cells
(i < s; s < i < t) are already output and no longer accessible. Therefore, H 1 (O) and
are always located at the rst and the second unlled cells and the machine
treats the tape as if it were [O[s];
Next, we consider how to input a modied Gray code expansion of a real number.
We dene our input mechanism so that nite input contains only approximation
information. Therefore, our machine should not recognize that the cell under the
head is ?, because the character ? with its preceding prex species the number
exactly. This requirement is also supported by the way an input tape is lled when
it is produced as an output of another machine; the character ? may be overwritten
by 0 or 1 in the future and it is impossible to recognize that a particular cell is left
eternally as ?. Therefore, our machine needs to have something other than the usual
sequential access.
To solve this, we consider multiple heads and consider that the machine waits for
multiple cells to be lled. Since at most one cell is left unlled, two heads are su-cient
for our purpose. Therefore, we consider two on an input tape
I, which move in the same way as output heads when they input characters. Note
that the character ? cannot be recognized by our machine, unlike the blank character
used by a Turing machine.
Thus, we dene a machine which has two heads on each input/output tape. Though
we have explaind this idea based on the modied Gray code expansion, this machine
can input/output sequences in  !
?;1 generally. In order to give the same computational
power as a Turing machine, we consider a state machine controlled by a set of computational
rules, which has some ordinary work tapes in addition to the input/output
tapes.
In order that the machine can continue working even when the cell under H 1 (I) or
for an input tape I is ?, we need, at each time, a rule applicable only reading
from H 1 (I) or H 2 (I). Therefore, the condition part of each rule should not include
input from both H 1 (I) and H 2 (I). This also means that, if both head positions of an
input tape are lled, we may have more than one applicable rules. Since a machine
may execute both rules, both computational paths should produce valid results.
To summarize, we have the following denition.
Denition 2 Let  be the input/output alphabet. Let be the work-tape alphabet
which includes a blank character B. An indeterministic multihead Type 2 machine
(IM2-machine in short) with k inputs is composed of the following:
tapes named I 1 ; I one output tape named O. Each tape T
has two heads
(ii) several work tapes with one head,
(iii) a nite set Q of states with one initial state q 0 2 Q,
(iv) computational rules of the following form:
Here, q and q 0 are states in Q, i j are heads of dierent input tapes, o is a head of
the output tape, w
, and w 00
are heads of work tapes, c j (j
c are characters from , d j and d 0
are characters from , and M j (j
are '+' or ' '. Each part of the rule is optional; there may be a rule without o(c),
for example. The meaning of this rule is that if the state is q and the characters
under the heads i are c j and d e , respectively,
then change the state to q 0 , write the characters c and d 0
the heads
, respectively, move the heads w 00
or backward depending on whether M move the heads of
input/output tapes as follows. For each when it is a head
moved to the position of H 2 (T ) and H 2 (T ) is moved
to the next cell, and when it is H 2 (T ), the position of H 1 (T ) is left unchanged
moved to the next cell.
The machine starts with the output tape lled with ?, work tapes lled with B, the
state set to q 0 , the heads of work tapes located on the rst cell, and the heads H 1 (T )
of an input/output tape T are located above the rst and the second cell,
respectively. At each step, the machine chooses one applicable rule and applies it.
When more than one rules is applicable, only one is selected in a nondeterministic
way.
Note 1. We can dene an indeterministic multihead Type 2 machine more generally
in that each input/output tape may have
input/output sequences in  !
. We dene the head movements after
an input/output operation as follows. If input/output is made from H l (T ) (l  n)
are moved to the position of H j+1 (T ) and H n+1 (T ) is moved
to the next cell. If input/output is made from H n+1 (T ) then H n+1 (T ) is moved to
the next cell. Note that when
?;0 is nothing but  ! and a tape has only one
head which moves to the next cell after an input/output.
Note 2. Here, we acted as if the full contents of the input tapes were given at the
beginning. However, an input is usually generated as an output of another machine,
and given incrementally. In this case, the machine behaves like this: it repeats executing
an applicable rule until no rule is applicable, and waits for input tapes to be
lled so that one of the rules become applicable, and repeats this process indenitely.
Note 3. A machine can have dierent input/output types on the tapes. The in-
put/output types we consider are
?;n (n  0) and   , where we may write  ! for
?;0 . We extend an IM2-machine with a sequence (Y indicating that it
has k input tapes with type Y one output tape of type Y 0 . When
Y i is  !
?;n , the corresponding tape has the properties written in Note 1. When Y i
is   , the corresponding tape has the alphabet  [ fBg and it has one head which
moves to the next cell when it reads/writes a character. In this case, the blank cells
are initialized with B. In addition, when Y 0 is   , we consider that the machine has
a halting state at which the machine stops execution.
Gray Code Computability of Real Functions
As we have seen, an IM2-machine has a nondeterministic behavior and thus it has
many possible outputs to the same input. Therefore, we consider that an IM2-machine
computes a multi-valued function. Note that multi-valued functions appear naturally
when we consider computation over real numbers [Bra98].
Denition 3 An IM2-machine M with k inputs realizes a multi-valued function
?;1 if all the computational paths M have with the input tapes lled
with (p outputs, and the set of outputs forms a
subset of F (p We say that F is IM2-computable when it is realized by some
IM2-machine.
This denition can be generalized to a multi-valued function
for the case Y i is   or  !
Note that our nondeterministic computation is dierent from nondeterminism used,
for example, in a non-deterministic Turing machine; a non-deterministic Turing machine
accepts a word when one of the computational paths accepts the word, whereas
all the computational paths should produce valid results in our machine. To distin-
guish, we use the word indeterminism instead of nondeterminism following [She75]
and [Bra98].
Denition 4 A multi-valued function F : I I is realized by M if G(F ) is
realized by M . We say that F is Gray-code-computable if G - F - G 1 is IM2-
computable.
Denition 5 A partial function f : I k ! I is Gray-code-computable if it is
computable as a multi-valued function.
5 Equivalence to the Computability induced by the Signed Digit Repre-
sentation
Now, we prove that Gray code computability is equivalent to the computability induced
by a Type-2 machine and the (restricted) signed digit representation.
Denition 6 A Type-2 machine is an IM2-machine whose type includes only  !
and   , and whose computational rule is deterministic.
This denition is equivalent to the one in [Wei00].
Proposition 1 Let Y i be  ! or   There is an IM2-machine which
there is a deterministic IM2-machine which
computes F .
Proof: The if part is immediate. For the only if part, we need to construct a deterministic
machine from an indeterministic machine for the case that the input/output
tapes have only one head. Suppose that M is an IM2-machine which realizes F .
Since the set of rules of M is nite, we give a numbering to them. We can determine
whether or not each rule is applicable because the input tapes do not have the character
?. Therefore, we can modify M to construct a deterministic machine M 0 which
chooses the rst applicable rule with respect to the numbering. The result of M 0 to
uniquely determined and is in F (x).
Denition 7 A representation of a set X is a surjective partial function from  ! to
X.
If  is a representation of X and a -name of x.
Denition 8 I and - I be representations. We say that
- is reducible to - 0 (- 0 ) when there is a computable function f
that dom(-). We say that - and - 0 are equivalent ( - 0 )
when - 0 and - 0  -.
Denition 9 1) The signed digit representation  sd of I uses the alphabet
denoting 1, and it is a partial function  sd I dened on
such that a j 6= 1 and a l 6= 1g
and returns  1
a i  2 i to a 1 a
2) The restricted signed digit representation  sdr of I is a restriction of  sd to a
smaller domain
such that a j 6= 1 and a l 6= 1g
without the rst character a 1 (= 1).
By  sd , 3=8 has innitely many names
:. The domain of  sdr means that we do not use a name which lasts as
therefore 3=8 has only two  sdr -names
Proposition 2  sdr   sd .
Proof: It is an easy exercise to give an algorithm that converts a  sd -name to a
sdr -name.
Denition I be a representation of I. A multi-valued function
I is (-computable if there is a Type-2 machine M of type
that if -(p) 2 dom(F ), then M with input p produces an innite sequence q such that
A partial function is (-computable if it is computable as a multi-valued function.
This denition can easily be extended to a function with several arguments.
Equivalent representations induce the same computability notion on I. As we explained
in the introduction, the equivalence class to which signed digit representation
belongs induces a suitable notion of computability on real numbers.
Proposition 3 Let M be an IM2-machine which realizes a multi-valued function
be IM2-machines which realize multi-valued
functions
Suppose that Im(hG
Then, there is an IM2-machine M -hN which realizes the multi-valued function
Here, the composition of multi-valued
functions F and G is dened to be y 2
Proof: First, we consider the case We write N for N 1 . We use the input
tapes of N as those of M - N and the output tape of M as that of M - N . We use
a work tape T with the alphabet  [ fBg which connects the parts representing N
and M , and work tapes to simulate the head movements of the input tape of M and
the output tape of N . It is easy to change the rules of M and N so that M reads
from T and N writes on T . We also need to modify the rules so that it rst looks for
an applicable rule coming from M and if there is no such rule, then looks for a rule
coming from N . It is possible because the former rules do not access to the input
tapes and therefore a machine can determine whether a particular rule is applicable
or not.
When k > 1, we need to copy the input tapes onto work tapes so that they can be
shared by the parts representing N . We dene that it executes rules coming
from N i until it outputs a character, and then switch to the next part.
As we will show in Section 7, we have the followings.
Lemma 4 There is an IM2-machine of type (f1; 0; 1g
?;1 ) which converts a
sdr -name of x to G(x) for all x 2 I.
Lemma 5 There is an IM2-machine of type (f0; 1g !
G(x) to the  sdr -name of x for all x 2 I.
Now, we prove the equivalences.
Theorem 6 A multi-valued function F : I k ! I is Gray-code-computable i it is
Proof: Suppose that M is an IM2-machine which Gray code computes F . By composing
it with the IM2-machines in Lemma 4 and Lemma 5, we can form, by Proposition
3, an IM2-machine of type ((f1; 0; outputs a  sdr -name
of a member of F -names of x i are given. Therefore, we have a
desired Type-2 machine by Proposition 1.
On the other hand, suppose that there is a Type-2 machine which (( sdr
computes F . Since a Type-2 machine is a special case of an IM2-machine, again, by
composing the IM2-machines in Lemma 4 and Lemma 5, we can form an IM2-machine
which Gray code computes F .
6 Topological Properties
1g. In this section, we show that G from I to  !
?;1 is homeomorphic, and
therefore is a topological embedding.
Since the character ? may be overwritten by 0 or 1, it is not appropriate to consider
Cantor topology on  !
?;1 . Instead, we dene the order structure ? < 0 and ? < 1 on
our alphabet and consider the Scott topology on f0;
We consider its product topology on f0; its subspace topology
on  !
?;1 . Let " p denote the set fx j p  xg. Then, the set f" (d?
is a base of f0; From this, we have a base f"
?;1 .
Note that P corresponds to the states of output tapes of IM2-machines after a nite
time of execution, and " (d?
?;1 is the set of possible outputs of an IM2-machine
after it outputs d 2 P . Thus, if q 2 O for an open set O   !
?;1 and for an output q
of an IM2-machine, then this fact is available from a nite time of execution of the
machine. In this sense, the observation that open sets are nitely observable properties
in [Smy92] holds for our IM2-machine. We can prove the following fundamental
theorem in just the same way as we do for Type-2 computability and Cantor topology
on f0; 1g ! .
Theorem 7 An IM2-computable function f
?;1 is continuous.
Now, Im(G) is the set f0; 1g ! f0; 1g
?;1 . We also consider the
subspace topology on Im(G), which has the base f"
g. We consider the inverse image of this base by G. When d 2 f0; 1g
range over open intervals of the form
respectively, for m and i integers. Since these open intervals form a base of the unit
open interval I, I and Im(G) become homeomorphic through the function G. Thus,
we have the following:
Theorem 8 The Gray code embedding G is a topological embedding of I into  !
?;1 .
As a direct consequence, we have the following:
Corollary 9 A Gray-code-computable function f : I k ! I is continuous.
As an application of our representation, we give a simple proof of Theorem 4.2.6 of
which says that there is no eective enumeration of computable real numbers.
Here, we dene to be a computable sequence if there is an IM2-machine of
outputs G(x i ) when a binary name of i is given.
Theorem is a computable sequence, then a computable number x with
x exists.
be an IM2-machine which computes s i to the binary
name of i. By Proposition 1, we can assume that M is deterministic. This means that,
by selecting one machine, the order the output tape is lled is xed. Since s
either s i [2i] or s i [2i + 1] is written in a nite time. When s i [2i] is written rst, we
put rst, we put
not is dened as not
not Then, the resulting sequence t is computable and is in Im(G), but is not
equal to s i for (i 2 !). Therefore, G 1 (t) is not equal to x i because of the injectivity
of the representation.
7 Conversion with signed digit representation
As an example of an IM2-machine, we consider conversions between the Gray code
and the restricted signed digit representation. Recall that a  sdr -name of x 2 I is
given as a sequence 1 : xs with xs an innite sequence of f0; 1; 1g. In this section, we
consider xs as the  sdr -name of x.
Since the intervals represented by nite prexes of both representation coincide, the
conversions become simple automaton-like algorithms which do not use work tapes.
Example 1 Conversion from the signed digit representation to Gray code. It has the
type
simply write the head of the input tape as I. It has
four states (i; the initial state, and 12 rules:
In order to express this more simply, we use the notation of the functional language
Haskell as follows:
ds
ds
Here, where produces bindings of c and ds to the head and the tail of stog0
(xs,0,1), respectively. It is clear that the behavior of an IM2-machine can be expressed
using this notation with the state and the contents of the work tapes before
and after the head positions passed as additional arguments. In the program
stog0, the states are used to invert the output: the result of stog0(xs; 1; 0) is that of
stog0(xs; 0; 0) with the rst character inverted, and the result of stog0(xs; 0; 1) is
stog stog0 0
input tape
output tape
Fig. 3. The behavior of stog IM2-machine when it reads 0
that of stog0(xs; 0; 0) with the second character inverted. Therefore, we can simplify
the above program as follows:
ds where c : ds = stog xs
Here, nh is the function to invert the rst element of an innite list. That is,
not
not
not s:ds
The behavior of stog with input 0:xs is given in Figure 1. Here, a small circle on an
output head means to invert the output from that head before lling the tape.
The program stog is a correct Haskell program and works on a Haskell system.
However, if we evaluate stog([0,0.]), there will be no output because it tries to
calculate the rst digit, which is ?. Of course, tail(stog([0,0.])) produces the
answer [1,0,0,0,.
Next, we consider the inverse conversion, which is an example of Gray code input.
Example 2 Conversion from Gray code to signed digit representation. Now, we only
show a Haskell program. It has the type (f0; 1g !
In this case, indeterminism occurs and yields many dierent valid results: the results
are actually signed digit representations of the same number. This is also a correct
Haskell program. However, it fails to calculate, for example, gtos(stog([0,0.]))
because the program gtos, from the rst two rules, tries to pattern match the head
of the argument and starts its non-terminating calculation. Therefore, it fails to use
the third rule. This is a limitation of the use of an existing functional language. We
will discuss how to implement an IM2-machine as a program in Section 9.
These programs are based on the recursive structure of the Gray code and is not as
di-cult to write such a program as one might imagine. One can see from Figure 2
the following three recursive equations:
(1)
Here, (p). The rst equation corresponds to the fact that on the interval
with the rst bit 0, i.e. the left half of Figure 2, the remaining bits form a 1 / 2 reduction
of

Figure

2. The second equation corresponds to the fact that on the interval with the
rst bit 1, i.e. the right half of Figure 2, the remaining bits with the rst bit inverted
form a 1 / 2 reduction of Figure 2, and if we use the equation with parenthesis, we can
also state that the remaining bits form the reversal of Figure 2. These two equations
characterize Figure 2. One interesting fact about this representation is that we also
have the third equation. It says that on the interval with the second bit 1, i.e. the
middle half of Figure 2, the remaining bits with the second bit inverted form a 1 / 2
reduction of Figure 2.
From Equations (1), we have the following recursive scheme.
Here, g 1 is a function to calculate f(x) from f(2x) when 0 < x is a function to
calculate f(x) from f(2x 1) when 3 is a function to calculate f(x)
from derived immediately from this scheme.
On the other hand, Equations (1) can be rewritten as follows:
stog uses this scheme to calculate the gray code output. These recursive schemes are
used to derive the algorithm for addition in the next section.
8 Some simple algorithms in Gray code
We write some algorithms with respect to Gray code.
Example 3 Multiplication and division by 2. They are simple shifting operations.
(suppose that the input is 0 < x < 1/2)
Example 4 The complement x 7! 1 x. It is a simple operation to invert the rst
digit, i.e.,the nh function in Example 1. Note that with the usual binary representation
and the signed digit representation, we need to invert all the bits to calculate 1 x
and thus this operation needs to be dened recursively. We can also see that the
complement operation (x 7! k=2 n x) with respect to a dyadic number k=2 n+1 for
can be implemented as inverting one digit.
Example 5 Shifting x 7! x Addition with a dyadic number is
nothing but two continuous complement operations over dyadic numbers. In the case
of the rst axis is and the second axis is Therefore, the function
AddOneOfTwo
operates as x 7! x
Example 6 Addition
We consider addition x+y with 0 < x; y < 1. Since the result is in (0; 2), we consider
the average function
pl (0:as)
pl (1:as)
pl (0:as)
pl (1:as)
pl (a:1:as)
pl (a:1:0:as)
pl (a:1:0:as)
pl (a:1:0:as)
pl (a:1:0:as)
pl (0:0:as)
pl (1:0:as)
pl (0:a:1:as)
pl (1:a:1:as)
To calculate the sum with respect to the signed digit representation, we need to look
ahead two characters. It is also the case with the Gray code representation. Since it
does not have redundancy, we can reduce the number of rules from 25 to 13 compared
with the program written in the same way with the signed digit representation.
9 Extension to the Whole Real Line, Implementation, and Conclusion
We have dened an embedding G of I to f0; 1g !
?;1 based on Gray code, and introduced
an indeterministic multihead Type 2 machine as a machine which can input/output
sequences in f0; 1g !
?;1 . Since G is a topological embedding of I into f0; 1g !
?;1 , our IM2-
machines are operating on a topological space which includes I as a subspace. We
hope that this computational model will propose a new perspective on real number
computation.
In this paper, we only treated the unit open interval I = (0; 1). We discuss here how
this embedding can be extended to the whole real line R. First, by using the rst
digit as the sign bit: 1 if positive, 0 if negative, and ? if the number is zero, we can
extend it to the interval ( 1; 1). We can also extend it to (
by assuming that there is a decimal point after the k-th digit. However, there seems
to be no direct extension to all of the real numbers without losing injectivity and
without losing the simplicity of the algorithms in Section 7 and 8.
One possibility is to use some computable embedding of R into ( 1; 1), such as the
function arctan(x)=. It is known that this function is computable, and
therefore, we have IM2-machines which convert between the signed digit representation
of x 2 R and the Gray code of f(x) in ( 1; 1). Therefore, we can dene our
new representation as G 0 R). It is clear that this representation
embeds R into  !
?;1 , and all the properties we have shown in Section 4 to 6 hold if
we replace I with R and G with G 0 . In particular, the computability notion on R
induced by G 0 and IM2-machines is equivalent to the one induced by the signed digit
representation and Type-2 machiens. However, we will lose the symmetricity of the
Gray code expansion and simplicity of the algorithms in Section 7 and 8.
Another possibility is to introduce the character \." indicating the decimal point into
the sequence. In order to allow an expression starting with ? (i.e. integers of the
need to consider an expression starting with 0 because it should
be allowed to ll the ? with 0 or 1 afterwards. Thus, we lose the injectivity of the
expansion because we have 1:xs. We also have the same kind of di-culty if
we adopt the
oating-point-like expression: a pair of a number indicating the decimal
point and a Gray code on ( 1; 1).
Although this expansion becomes redundant, the redundancy introduced here by
preceding zeros is limited in that we only need at most one zero at the beginning
of each representation and thus each number has at most two names. As is shown
in [BH00], we need innitely many names to innitely many real numbers if we
use representations equivalent to the signed binary representation. Therefore, the
redundancy we need for this extension is essentially smaller than that of the signed
binary representation.
Finally, we show some experimental implementations we currently have. As we have
noted, though we can express the behavior of an IM2-machine using the syntax of a
functional language Haskell, the program comes to have dierent semantics under the
usual lazy evaluation strategy. We have implemented this Gray code input/output
mechanism using logic programming languages. We have written gtos, stog, and the
addition function pl of Section 8 using KL1 [UC90], a concurrent logic programming
language based on Guarded Horn Clauses. We have also implemented them using
the coroutine facility of SICStus Prolog. We are also interested in extending lazy
functional languages so that programs in Section 7 and 8 become executable. The
details about these implementations are given in [Tsu00].

Acknowledgements

The author thanks Andreas Knobel for many interesting and illuminating discus-
sions. He also thanks Mariko Yasugi, Hiroyasu Kamo, and Izumi Takeuchi for many
discussions.



--R

A data structure based on gray code encoding for graphics and image processing.
Exact real arithmetic: A case study in higher order programming.
Topological properties of real number representations.
Recursive and Computable Operations over Topological Structures.
The New Turing Omnibus.
A new representation for exact real numbers.

Real number computability and domain theory.
A golden ratio notation for the real numbers.
An abstract data type for real numbers.
On the de
Haskell report.
The takagi function and its generalization.
Computability in Analysis and Physics.
Computation over abstract structures: serial and parallel procedures.

Implementation of indeterministic multihead type 2 machines with ghc for real number computations.
On computable real numbers
Design of the kernel language for the parallel inference machine.
Exact real computer arithmetic with continued fractions.
Type 2 recursion theory.
An introduction to computable analysis.
--TR
Exact Real Computer Arithmetic with Continued Fractions
Design of the kernel language for the parallel inference machine
Topology
Real number computability and domain theory
A domain-theoretic approach to computability on the real line
An abstract data type for real numbers
Exact real arithmetic: a case study in higher order programming
Computable analysis
Topological properties of real number representations
A golden ratio notation for the real numbers

--CTR
Hideki Tsuiki, Compact metric spaces as minimal-limit sets in domains of bottomed sequences, Mathematical Structures in Computer Science, v.14 n.6, p.853-878, December 2004
multihead;gray code;indeterminism;IM2-machines;real number computation