# Real Functions Computable by Finite Automatons using Affine
Representations

Michal Konečnư, Proceedings of CCA 2001 Dagstuhl Seminar,
Theoretical Computer Science, 284(2):373-396, July 2002
## Abstract

This article 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
article considers so-called affine representations where numbers
are represented by infinite compositions of affine contracting
functions on $I$. Affine representations include the radix
(\eg~decimal, signed binary) representations.

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 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

Michal Konečnư
Last modified: Mon Mar 10 11:52:51 GMT 2003