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ý