Abstract :
After a short introduction to on-line computing, we prove that the functions computable in on-line by a finite automaton are piecewise affine functions whose coefficients are rational numbers (i.e., the functions f(x)=ax+b, or f(x,y)=ax+by+c where a, b, and c are rational). A consequence of this study is that multiplication, division and elementary functions of operands of arbitrarily long length cannot be performed using bounded-size operators
Keywords :
computability; digital arithmetic; finite automata; arbitrarily long length; division; elementary functions; finite automaton; multiplication; online computing; operands; piecewise affine functions; rational numbers; Algorithm design and analysis; Automata; Character generation; Computer architecture; Delay; Digital arithmetic; Fixed-point arithmetic; Partial response channels; Performance evaluation; Pipeline processing;
