Graphics Reference
In-Depth Information
Figure 5.49.
State diagram for Example
5.11.1.
Figure 5.50.
Computing the greatest
integer in x.
been developed that formalizes the notion of a machine over the reals. See [BlSS89]
or [GHSV93]. We would like to mention a few of the highlights of the theory in this
section.
We motivate our definition of a machine over the reals with two examples from
[BlSS89].
5.11.1 Example.
Let g :
C
Æ
C
be a complex polynomial map. Since the highest
order term of g dominates, one can show that there exists a positive constant C
g
so
that |
z
| > C
g
implies that |g
k
(
z
)| Æ•as k goes to infinity. Figure 5.49 shows a flow-
chart for an algorithm based on g. Right now we prefer to think of it as a state diagram
for a machine M. Clearly, M will halt precisely on those inputs
z
for which |g
k
(
z
)| Æ
• as k goes to infinity.
5.11.2 Example.
Figure 5.50 shows an algorithm that computes the greatest
integer Îx˚ for x Œ
R
, x ≥ 0. We again shall think of it as a state diagram of a machine
that operates on a pair (k,x). To find the greatest integer in x, one inputs (0,x).
