Prüfungsprotokoll Diplomprüfung Berechenbare Analysis

Prüfer:Prof.Dr. Weihrauch
Beisitzer:Dr. Hertling
Datum:09.08.2001
Dauer:40 min (vierzig in Buchstabennotation)
Note:1.3

Ausdehnung des Berechenbarkeitsbegriffs auf reelle Zahlen. Welche Probleme tauchen auf?

abzählbare Mengen (N,Q) und überabzählbare Mengen (R)

Mit endlichen Zeichenreihen kommt man nicht weit. Deshalb unendliche Zeichenketten, Erweiterung der Turing Maschine zur Typ 2 Maschine
Darstellungen? Was sind sie?

Surjektive Funktionen unendlicher Zeichenketten auf R

Welche Berechenbarkeit ist möglich? Addition und Multiplikation mit der Dezimaldarstellung möglich?

Nein, mit Begründung. Das Präfix des Ergebnis ist durch weit rechts liegende Dezimalstellen nicht bestimmt. Deshalb andere Darstellungen (Naive Cauchy, Rho <, Rho >, Rho Cauchy) Die naive Cauchy ist unbrauchbar, weil keine Konvergenzgeschwindigkeit existiert.
Cauchydarstellung deshalb weil das Cauchykonvergenzkriterium benutzt wird. Näherung durch Approximation durch rationale Zahlen

Potenzreihen? Wann sind sie berechenbar?

Nicht jede ist bb.
Definition einer Potenzreihe
Voraussetzung für Berechenbarkeit: Konvergenzradius lim, sup
(sqrt((n(an)), bb. Koeffizienten, Konstante M

Funktionendarstellung

Voraussetzung für die Funktionendarstellung ist, die abzählbare dichte Basis von R aus rationalen Kugeln Paare offener Kugeln. f-1(I(w)) = Def(f) geschnitten mit der Vereinigung von f(vi) wenn wi = vi und die Kugelpaare sind. (Definition auf der 1. Seite von KE 6)

Was kann man denn machen mit der Funktionendarstellung Delta?

Auswerten der Funktion mit einem x aus dem Definitionsbereich.
Die Verknüpfung von 2 Funktionen ist (Delta, Delta, Delta) bb.

Mengen in Rn? Welche Mengen sind entscheidbar in Rn?

nur 2

Warum nur 2?

Rekursiv aufzählbare Mengen sind offen.Damit eine Menge entscheidbar ist, muß auch ihr Komplement offen sein, die Menge selbst also offen und abgeschlossen, entweder R oder {}.

Was kann man tun dagegen?

Definition der rekursiven Menge für eine abgeschlossenen Menge, die entweder leer ist, oder über die Abstandsfunktion dA(x) = inf d(a,x) für alle x aus A

Rekursiv aufzählbare, Co-rekursiv aufzählbare Mengen?

Definition für abgeschlossene Mengen Rechts und Linksberechenbarkeit der Abstandsfunktion.(Rho <, Rho >)

Ist die x-Achse in R*R rekursiv?

Ja (Abstandsfunktion ist der Betrag von y )

Wie werden Mengen reeller Zahlen dargestellt?

Wieder über eine abzählbare Basis. Zeichnung von rekursiven aufzählbaren Mengen und co-r.a. Mengen geschlossene Kugeln überdecken das Komplement der co-r.a. Menge (alpha >) offene Kugeln schneiden die r.a. Menge (alpha <) Rekursive Menge über <p,q> wobei p ein alpha < und q ein alpha > Name ist.

Nullstellen. Sind die berechenbar aus der Funktionsdarstellung?

Nicht isolierte Nullstellen sind nicht bb. Beinahe Nullstellen können, falls sie existieren, beliebig angenähert werden. Trisektionsverfahren. Funktioniert über Dreiteilung eines geschlossenen Intervalls mit f(a) * f(b) < 0. Voraussetzung: Streng monoton, stetig auf dem gesamten Funktionsbereich und nur eine Nullstelle


Anmerkung

Nach nur vierzig Minuten war die Prüfung schon wieder vorbei. Das Skript von Dr. Hertling (Studientage 1681 21./22. Juli 2001) ist hilfreich zur Veranschaulichung. Der wichtigste Satz steht auf der ersten Seite, nämlich daß es sich um einen informellen Überblick handelt. Aber die Mathematik ist auch an formale Definitionen und Sätze gebunden. Darauf legt Prof. Weihrauch auch Wert. Er legt sich aber nicht zu sehr auf die formalen Dinge fest. Die Berechenbare Analysis wurde in 2 Kurse gespalten (1681 und 1838). Prof. Weihrauch hat während der Prüfung in den Kurseinheiten geblättert und Fragen aus dem Skript gestellt. Zusatzinfos aus anderen Kursen oder Büchern wurden nicht geprüft. Prüfungsatmosphäre relativ entspannt. Benotung sehr fair.

Stefan