Real functions computable by finite automata

Achim Jung, Birmingham

Abstract: Based on the work of a number of researchers, Peter Potts and
Abbas Edalat have developed a framework for real-number computation which
is both expressive and elegant. In his thesis, Peter Potts shows how to
compute all standard mathematical functions in this framework. His
algorithms are derived from classical formulas for continued fractions. In
his presentation, a calculation always corresponds to a (potentially
infinite) expression tree, which consists of tensors and matrices at its
nodes, into which the input stream(s) are fed at (potentially infinitely
many) leaves, and which creates an output stream from its root.

Reinhold Heckmann showed that in the simple situation where the tree
consists of a single matrix, this matrix must contain larger and larger
entries as the computation proceeds. He gives necessary and sufficient
conditions for when the entries can be bounded by a constant.

In this talk, I report on work done by Michal Konecny at Birmingham, who
has extended Heckmann's work in two directions: He considers general
finite automata rather than expression trees, and he allows arbitrary
digit systems to be used. His main result is that a differentiable
function, which is computed by a finite automaton, must be equal to a
linear fractional transformation. (By Heckmann's results, this linear
fractional transformation must furthermore be of a very special kind.)