Graphics Reference
In-Depth Information
What is notable about the two examples here is the state diagram of the
“machines” that carried out the associated algorithms. This is what we want to gen-
eralize now.
Let R be an ordered commutative ring with unity. Because there is no space to go
into lots of details, the definitions we give here will not be as general as they could be
but are aimed at the special cases R =
Z
or
R
.
Definition.
A
machine M over R
consists of three sets I = R
m
(the
input space
), O =
R
n
(the
output space
), and S = R
k
(the
state space
), along with a finite connected
directed graph G whose nodes are one of four types:
Input node
: There is only one node of this type and it will be denoted by 1.
It has no incoming edge and only one outgoing edge to a node
denoted by b(1) and called the
next node
. Associated to this node
is a linear injective map i :I Æ S. One thinks of i as just taking
the input and “putting it into the machine.”
Output node
: These nodes have no outgoing edges. Associated to each such
node o, there is a linear map g
o
:S Æ O.
Computation node
: Each such node c has a unique outgoing edge to a node denoted
by b(c) and called the
next node
. Associated to the node is a poly-
nomial map g
c
:S Æ S. If R is a field, then we can let g
c
be a
rational function.
Branch node
:
Each such node b has precisely two outgoing edges to nodes
denoted by b
-
(b) and b
+
(b) called
next nodes
. Associated to b is
a polynomial h
b
:S Æ R, such that b
+
(b) and b
-
(b) are associ-
ated to the conditions h
b
(x) ≥ 0 and h
b
(x) < 0, respectively.
By expressing the definition of a machine over a ring graphically, it is not as com-
plicated as it may sound. It leads to state diagrams just like in the Turing machine
case. The two examples above are, in fact, special cases of a machine M over the reals.
In Example 5.11.1, we identify the complex numbers
C
with
R
2
. The input, output,
and state spaces of M are all
R
2
. The function i associated to the input node is the
identity map and the function at the branch node is h(
z
) = |
z
|
2
- C
g
. In Example 5.11.2,
the input, output, and state spaces are
R
,
R
, and
R
2
, respectively. The function asso-
ciated to the input node is the function from
R
to
R
2
that maps x to (0,x). At com-
putation nodes, the associated function is (x,y) Æ (x + 1,y - 1). The output function
is the map from
R
2
to
R
that maps (x,y) to y.
Now, given a machine M over a ring R with nodes N, define a partial map
GN S
:
¥Æ ¥
N S
by G (n,s) = (n¢,s¢) where
(1) G is not defined if n is an input or output node.
(2) If n is a computation node, then n¢=b(n) and s¢=g
n
(s).
(3) If n is a branch node, then s¢=s and n¢=b
+
(n) if h
n
(s) ≥ 0 and n¢=b
-
(n) if
h
n
(s) < 0.
