Analytische Maschinen

Abstract

In dieser Arbeit präsentieren wir einige Resultate über analytische Maschinen hinsichtlich des Berechenbarkeitsbegriffs über Q und R, der Lösungen von Differentialgleichungen und des Stabilitätsproblems dynamischer Systeme. Wir erläutern zuerst das Maschinenmodell, das eine Art von BLUM-SHUB-SMALE Maschine darstellt, erweitert um unendliche, konvergente Berechnungen. Danach vergleichen wir die Mächtigkeit dieses Berechnungsmodells über den Körpern Q und R und zeigen z.B., daß endliche Berechnungen mit reellen Zahlen durch unendliche, konvergente Berechnungen mit rationalen Zahlen simuliert werden können, wobei die Genauigkeit der Approximation während des Prozesses nicht bekannt ist. Analytische Berechnungen über R sind echt mächtiger als über Q. Unsere Aufmerksamkeit wendet sich dann gewöhnlichen Differentialgleichungen (DGl) zu, bei denen wir hinreichende Kriterien für die Berechenbarkeit von Lösungen innerhalb unseres Modells angeben. Schließlich untersuchen wir dynamische Systeme, die durch DGl beschrieben werden, und zeigen die Unentscheidbarkeit einer Klasse von Stabilitätsproblemen für dynamische Systeme.

In this thesis we present some results about analytic machines regarding computability over Q and R, solutions of differential equations, and the stability problem of dynamical systems. We first explain the machine model, which is a kind of BLUM-SHUB-SMALE machine enhanced by infinite convergent computations. Next, we compare the computational power of such machines over the fields Q and R showing e.g. that finite computations with real numbers can be simulated by infinite converging computations on rational numbers, but the precision of the approximation is not known during the process. Analytic computations over R are strictly more powerful than over Q. Our attention is then shifted to ordinary differential equations (ODEs) where we establish sufficient criteria for the computability of their solutions within our model. We investigate dynamical systems described by ODEs and show the undecidability of a class of stability problems for dynamical systems.