# Real Functions
Computable by Finite Transducers using Affine IFS
Representations

Michal Konecny, Technical Report, July 2000
## Abstract

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