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