Analytische Maschinen und Berechenbarkeit analytischer Funktionen

Abstract

Gegenstand dieser Arbeit ist der Berechenbarkeitsbegriff über den reellen und komplexen Zahlen und die Charakterisierung der Berechenbarkeit analytischer Funktionen. Dazu werden analytische Maschinen betrachtet, ein von Hotz eingeführtes Maschinenmodell, das die von Blum, Shub und Smale definierten Maschinen um unendliche konvergente Berechnungen (analytische Berechnungen) erweitert. Es werden Resultate über die Eigenschaften analytisch berechenbarer Funktionen präsentiert und Verallgemeinerungen des Darstellungssatzes von Blum, Shub und Smale für R-berechenbare Funktionen gegeben. Das Maschinenmodell wird dann dazu benutzt, um Berechenbarkeit holomorpher (komplex-analytischer) Funktionen zu charakterisieren. Für die in der Arbeit definierte Klasse der koeffizientenberechenbaren analytischen Funktionen wird gezeigt, daß sie unter grundlegenden Operationen wie Komposition und lokaler Umkehr abgeschlossen ist. Es wird ferner gezeigt, daß die analytische Fortsetzung einer auf einem Gebiet D C analytischen und berechenbaren Funktion auf ein Gebiet G D ebenfalls wieder berechenbar ist. Zusätzlich zur Berechenbarkeit durch Maschinen wird auch Berechenbarkeit mittels rekursiver Funktionen betrachtet. Die linear primitiv-rekursiven Funktionen werden eingeführt und im Rahmen der μ-rekursiven Funktionen klassifiziert.

The subject of this thesis is computability over the real and complex numbers, and the characterization of computable analytic functions. To this end, we consider analytic machines, a machine model introduced by Hotz that extends the machines defined by Blum, Shub and Smale with infinite convergent computations (analytic computations). Results concerning the properties of analytically computable functions are presented and generalizations of Blum, Shub and Smale's representation theorem for R-computable functions are given. Then, the machine model is used for the characterization of computability of holomorphic (complex-analytic) functions. The class of coefficient-computable analytic functions is introduced and shown to be closed under basic operations such as composition and local inversion. Further, it is shown that, given a function that is analytic and computable on a region D C and which possesses an analytic continuation on a region G D, this analytic continuation is also computable. In addition to computability by machines, computability by recursive functions is considered. The linear primitive-recursive function are introduced and classified within the μ-recursive functions.