Many-Valued Real Functions Computable by Finite Transducers using IFS-Representations

Michal Konecny, PhD thesis, final version of October 2000


We try to classify many-valued functions of type $I_1\x\cdots\x I_n\multo I_0$ (for some compact intervals $I_i\subseteq\R$) that can be exactly realized by a finite transducer using some stream representation of the real numbers. We restrict our study to the so-called IFS-representations where numbers are represented by infinite compositions of contracting functions on a compact interval. IFS-representations include the radix (e.g.~decimal, signed binary) representations and representations based on Möbius transformations (=LFT's).

We prove that a many-valued function which is computable by a finite transducer using IFS-representations with contractions that contract strongly enough, is locally `distorted'-affine wherever it is locally single-valued and continuously differentiable. In the proof we use a technique which lets us treat any sufficiently strong contraction as an affine contraction. The theorem entails that a function computable by a finite transducer using affine (resp.~LFT-) representations, is locally equal to some $n$-ary affine function (resp.~LFT).

We also prove that many-valued $n$-ary piecewise affine functions with rational coefficients are computable by a finite transducer using the signed binary representation. We exhibit an example of a finitely computable function which is strictly increasing, has zero derivative on a dense set, and infinite derivative on another dense set.

BibTeX, ps.gz(a4 double-sided), erratum
Michal Konecny
Last modified: Mon Mar 10 11:53:21 GMT 2003