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

Michal Konecny, PhD thesis, final version of October 2000
## Abstract

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