Real Functions Computable by Finite Transducers using Affine IFS Representations

Michal Konecny, Technical Report, July 2000


This report tries to classify the functions of type $I^n\to I$ (for some interval $I\subseteq\R$) that can be exactly realized by a finite transducer. Such a class of functions strongly depends on the choice of real number representation. This report considers so-called IFS representations where numbers are represented by infinite compositions of contracting functions on $I$. IFS representations include the radix (e.g.~decimal, signed binary) and LFT representations. The results in this report apply to those IFS representations that use affine contractions, like the radix representations, for example.

The first result is that all piecewise affine functions of $n$ variables with rational coefficients are computable by a finite transducer which uses the signed binary representation. The second and main result is that any function computable by a finite transducer using an affine IFS representation is affine on any open connected subset of $I^n$ on which it is continuously differentiable. This limitation theorem shows that the set of finitely computable functions is very restricted.

BibTeX, ps.gz(a4), ps.gz(letter).
Michal Konecny
Last modified: Mon Mar 10 11:51:36 GMT 2003