Computing with dynamical systems (Q2461404)

The article discusses the use of techniques from the theory of discrete dynamical systems for the formal analysis of algorithms in computer science. The author combines Knuth's definition of an algorithm with some ideas of Dijkstra and Gries obtaining the so-called mapcode formalism that represents an algorithm as a commutative diagram containing a discrete dynamical systems. Statements about the termination or correctness of the algorithm are then translated into the language of dynamical systems. As concrete examples the total correctness of several simple algorithms, in particular for gcd computations, is proven within this formalism.