# Real Functions Incrementally Computable by Finite
Automatons

Michal Konecny, Technical Report, October 1998
## Abstract

This is an investigation into exact real number computation using
the incremental approach of
[Potts98,Edalat-Potts97,Nielsen-Kornerup95,Vuillemin90] 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\to\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 representation, we can
classify functions that are finitely computable in this
representation and are continuously differentiable almost
everywhere. They are exactly those functions whose graph is a
fractured line connecting points with rational coordinates.

BibTeX,
ps.gz(a4),
ps.gz(letter).

Michal Konecny
Last modified: Mon Mar 10 11:51:21 GMT 2003