# Real Functions Incrementally Computable
by Finite Automata

Michal Konečnư, Proceedings of MFPS 1998, Theoretical Computer
Science, to appear
## Abstract

This is an investigation into exact real number computation
using the incremental approach of Vuillemin, Nielsen, Kornerup,
Potts, Edalat and others where numbers are represented as
infinite streams of digits, each of which is a Möbius
transformation. The objective is to determine for each
particular system of digits which functions R→R can be computed
by a finite transducer and ultimately to search for the most
finitely-expressible Möbius representations of real numbers.
The main result is that locally such functions are either not
continuously differentiable or equal to some Möbius
transformation. This is proved using elementary properties of
finite transition graphs and Möbius transformations. Applying
the results to the standard signed digit representations, we can
classify functions that are finitely computable in such a
representation and are continuously differentiable everywhere
except for finitely many points. They are exactly those
functions whose graph is a fractured line connecting finitely
many points with rational coordinates.

BibTeX
ps.gz (a4 preprint)

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