Abstract

We study the question, which functions of the type R^n->R can be computed by a finite state machine. The answer depends on the representation of the real numbers. We consider the class of IFS (Iterated Function System) representations that generalize the standard radix representations as well as the Moebius transformation representations used by Edalat and Potts. In this approach real numbers are represented by infinite series of contracting functions called digits (most commonly (x-1)/2, x/2 and (x+1)/2 restricted to [-1,1] in the case of the signed binary representation).

We restrict ourselves to functions that are differentiable almost everywhere, because even for the standard representations there are finitely computable functions whose graph is fractal-like, e.g.~a function that has a derivative equal to zero on a dense set but also equal to infinity on another dense set.

In the case of representations where all digits are affine functions it is relatively easy to observe that any such finitely computable differentiable function must be affine. This result can be extended to almost arbitrary digit functions by a translation D |-> T o D o T^{-1} where T is a bijection chosen so that the right hand side is an affine function. Especially, such a translation exists for any continuously differentiable contraction D whose derivative is everywhere positive and which has a second derivative in its fixpoint.