TIA: Berechenbarkeit auf anderen Mengen (Lernziele KE7, 2/2)

Update: Kleine Korrektur nach Einwand von Phil in den Kommentaren.

Update: es hat sich ein Fehler eingeschlichen bei der Definition der Dualnotation. Sollte nun behoben sein. Danke Thomas.

Update: das ist nun der letzte Beitrag, der auf die Lernziele gemünzt wird. Irgendwie verlässt mich immer kurz vor Schluss die Lust mich durch die quälenden Definitionen zu... ähm... nunja... quälen.

Da ich im Moment mit KE4 von 1658 (TIB) nicht weiterkomme, bin ich mal der Bitte von Marco nachgekommen und habe die Zusammenfassung von KE7/1657 fertig gemacht. Hoffentlich hilft sie euch etwas.

Lernziel 3

Erklärung der Reduzierbarkeit und Äquivalenz von Nummerierungen

Die Reduzierbarkeit haben wir bereits im Beitrag zu KE6 gehabt. Ähnlich verhält es sich hier.

Wir machen es uns am liebsten leicht: wozu die Berechenbarkeitsmodelle aller Nummerierungen durchgehen wenn wir sie aufeinander reduzieren und so ihre Äquivalenz nachweisen können? So können wir uns einfach, wie im Falle der Standardnummerierung $\varphi$, unter bestimmten Bedingungen auf eine Nummerierung festlegen wenn wir zeigen können, dass die anderen Nummerierungen zu dieser äquivalent sind oder auf unsere reduziert werden können.

Da jede Menge $M$ mit mind. zwei Elementen sehr viele Nummerierungen hat, die Berechenbarkeitskonzepte (siehe vorheriger Beitrag) auf diesen Mengen festlegen, brauchen wir was um diese zu vergleichen. Das Konzept der Reduzierbarkeit erscheint noch etwas willkürlich, wir werden es aber im Teil B der theoretischen Informatik im Rahmen der Komplexitätstheorie wieder treffen und anwenden. Also am besten nicht überspringen.

Beispiel: $id_{\mathbb{N}}\leq\nu_{\mathbb{Z}}$

Wir wollen hier zeigen, dass wir $id_{\mathbb{N}}$ auf $\nu_{\mathbb{Z}}$ reduzieren können, d.h. wir brauchen eine Funktion die als Definitionsbereich $id_{\mathbb{N}}$ und als Bildbereich $\nu_{\mathbb{Z}}$ hat. Dazu müssen wir nur eine einstellige und totale  Funktionen $f$ aus $R^{(1)}$ wählen, die das für uns erledigt. Selbstverständlich muss sie auch berechenbar sein.

Wir rekapitulieren nochmal die zwei Nummerierungen :

$id_{\mathbb{N}}: \mathbb{N}\Rightarrow\mathbb{N},id_{\mathbb{N}}(k) = k$ für alle $k\in\mathbb{N}$

Identitätsfunktion also. Wir bilden eine Zahl aus $\mathbb{N}$ auf sich selbst ab, z.B. $id_{\mathbb{N}}(5)=5$. That's it. Wie man sieht ist die Nummerierung total (für jedes Element aus der Definitionsmenge haben wir ein  Element aus der Bildmenge) und bijektiv (das Bild ist sogar eindeutig, d.h. wir können auch eine Inverse draus basteln).

$\nu_{\mathbb{Z}}: \mathbb{N}\Rightarrow\mathbb{Z},\nu_{\mathbb{Z}}<i,j> = i-j$ für alle $i,j\in\mathbb{N}$

Wir bilden eine Zahl aus $\mathbb{N}$ auf eine Zahl auf $\mathbb{Z}$ ab, z.B. $\nu_{\mathbb{Z}}(500)=<27,4>=27-4=23$ (falls bei euch nun wieder Fragezeichen über euren Köpfen auftauchen, erinnert euch bitte an die Inverse der Cantorschen Tupelfunktion).

Wie man sieht ist die Nummerierung auch total (für jedes Element aus der Definitionsmenge haben wir ein  Element aus der Bildmenge), aber nicht bijektiv, wie man leicht am folgenden Beispiel sieht:

$\nu_{\mathbb{Z}}(277)=<24,1>=24-1=23$

$\nu_{\mathbb{Z}}(500)=<27,4>=27-4=23$

Damit würden die Zahlen $500$ und $277$ aus dem Definitionsbereich $id_{\mathbb{N}}$ auf die gleiche Zahl im Bildbereich $\nu_\mathbb{Z}$ unserer "Übersetzungsfunktion" abgebildet, eine Inverse können wir so zwar nicht angeben, ist aber nicht schlimm. Die brauchen wir hier ja auch nicht.

Besorgen wir uns also eine Funktion $f: id_\mathbb{N}\Rightarrow\nu_{\mathbb{Z}}$.

Es gilt also $Def(f)=id_{\mathbb{N}}$ und $Bild(f)=\nu_{\mathbb{Z}}$: zu jedem Element der einen Nummerierung gibt es ein Element aus der anderen Nummerierung. Eine Möglichkeit für die Übersetzungsfunktion $f$ wäre z.B. $f(i) = <i,0>$. Versuchen wir es doch einfach mal:

$id_{\mathbb{N}}(500) = 500$

$f(500) = <500,0> = 124251$

$\nu_{\mathbb{Z}}(124251) =<500,0>=500-0=500$

Sieht gut aus. Damit ist $id_{\mathbb{N}}\leq\nu_{\mathbb{Z}}$. In Worten: $id_{\mathbb{N}}$ ist reduzierbar auf $\nu_{\mathbb{Z}}$.

Diese Nummerierungen haben einige wichtige Eigenschaften, die wir hier festhalten wollen:

$(\nu_1\leq\nu_2$ und $\nu_2\leq\nu_3)\Rightarrow\nu_1\leq\nu_3$

$(\nu_1\equiv\nu_2$ und $\nu_2\equiv\nu_3)\Rightarrow\nu_1\equiv\nu_3$

Die beiden Eigenschaften der Reduzierbarkeit und Äquivalenz der Nummerierungen basieren auf der Transitivität. Also nichts neues.

Was vielleicht noch erwähnenswert ist: Bei der Übersetzung durch die totale Übersetzungsfunktion $f$ gehen Berechenbarkeitsinformationen verloren geht. Damit ist die überführte Nummerierung "reichhaltiger", die Ziel-Nummerierung "ärmer".

Erst wenn wir zwei Nummerierungen haben, die Äquivalent sind, so induzieren Sie das selbe Berechenbarkeitskonzept. Wir erinnern uns nochmal an die Definition aus Kurseinheit 5:

Es seien $\nu_1:\subseteq\mathbb{N}\rightarrow{M_1}$ und $\nu_2:\subseteq\mathbb{N}\rightarrow{M_2}$ Nummerierungen.

1. $\nu_1\leq\nu_2$ ($\nu_1$ ist reduzierbar/übersetzbar auf $\nu_2$) genau dann wenn es ein $f\in P^{(1)}$ gibt mit $\nu_1(i)=\nu_2\circ f(i)$ für alle $Def(\nu_1)$

2. $\nu_1\equiv\nu_2$ ($\nu_1$ ist äquivalent zu $\nu_2$), genau dann wenn $\nu_1\leq\nu_2$ und $\nu_2\leq\nu_1$.

Unsere Nummerierungen sind also Äquivalent wenn sie ineinander übersetzbar sind. Wir haben damit beide Mengen vollständig nummeriert und kein Element aus ihnen ausgelassen.

Das führt uns zur Kernaussage des Lernziels:

Zwei Nummerierungen einer Menge $M$ induzieren auf $M$ dasselbe Berechenbarkeitskonzept wenn sie äquivalent sind.

Antwort zum Lernziel: Eine Nummerierung ist auf eine andere reduzierbar wenn wir sie durch einen totale, berechenbare Funktion in die andere "übersetzen" können. Leider gehen bei diesem Vorgang evtl. Berechenbarkeitsinformationen verloren, da wir nur noch auf den Nummern der Elemente arbeiten.

Können zwei Nummerierungen gegenseitig aufeinander reduziert werden, so sind diese Äquivalent und induzieren auf der nummerierten Menge dasselbe Berechenbarkeitskonzept

Lernziel 4

Konstruktion einer reellen Zahl $x$ einer Funktion $\nu:\mathbb{N} \rightarrow \mathbb{R}$, die nicht im Bild von $\nu$ liegt

Kommen wir nun zur zentralen Aussage dieser Kurseinheit. Genau darum drehte sich unsere ganze Vorarbeit in den Lernzielen Eins bis Drei.

Die Aussage ist:

Reelle Zahlen können wir nicht nummerieren, da es davon überabzählbar viele gibt.

Ihr erinnert euch sicher an den Überabzählbarkeitsbeweis von $\mathbb{R}$ mittels Diagonalisierung? Wenn nicht, schaut bitte nochmal im Beitrag zu KE4 im Abschnitt "zweites Diagonalisierungsargument von Cantor" nach. Die Menge der reellen Zahlen nicht mehr abzählbar (sie ist mächtiger als $\mathbb{N}$) und kann deswegen durch diese auch nicht nummeriert werden, was wir auf reelle Funktionen übertragen können. Die obige Aussage, formal dargestellt, bedeutet:

Es sei $\nu :\mathbb{N}\rightarrow{\mathbb{R}}$. Dann gibt es eine reelle Zahl $x$ mit $x\notin Bild(\nu)$.

Wenn wir also die reellen Zahlen nummerieren wollen, so gelingt uns das nicht und wir haben immer noch eine reelle Zahl, die nicht nummeriert ist. Der Beweis mittels Diagonalisierung ist im verlinkten Beitrag zu KE4 zu finden.

Ich habe mir das Leben etwas einfacher gemacht und einfach auf das zweite Diagonalisierungsargument verwiesen. Gefragt wurde aber nach einer expliziten Funktion $\nu$, für die ein $x$ zu konstruieren ist, welches nicht im $Bild(\nu)$ liegt. Machen wir das doch.

Konstruktion einer Zahl $x$, die nicht im Bild von $\nu$ liegt

Wir nehmen das gleiche Verfahren, wie im Diagonalisierungsargument und nehmen an, dass $\nu$ alle Zahlen im geschlossenen, reellen Intervall zwischen $0$ und $1$ nummeriert.

$\nu(0)=0,000001...$

$\nu(1)=0,000002...$

Das ist etwas komisch dargestellt und sicherlich keinesfalls mathematisch korrekt. Aber da die Zahlen unendlich lang sind, kann ich sie natürlich nicht ausschreiben. Das sollte nur verdeutlichen was wir nummerieren.

Wir tun also einfach mal so, als hätten wir alle Zahlen aus dem Intervall nummeriert.

Nun basteln wir uns eine Funktion $h$, die alle natürlichen Zahlen $i\in\mathbb{N}$ durchgeht, die nummerierten Elemente $\nu(i)\in\mathbb{R}$ nimmt und die $i$-te Stelle nach dem Komma dieses Elements um eines hochzählt und so daraus eine neue Zahl $x\in\mathbb{R}$ bastelt.

Offensichtlich ist diese Zahl $x$ mit $\nu(?)=x$ an jeder Stelle $i$ von der Stelle $i$ eines jeden $\nu(i)\in\mathbb{R}$ verschieden. Wir haben also tatsächlich eine neue Zahl $x\in\mathbb{R}$ gefunden, die wir nicht nummeriert haben. Obwohl wir von der Vollständigkeit unserer Nummerierung ausgegangen sind (daher das $?$ in $\nu(?)=x$).

Antwort zum Lernziel: Aufgrund der Überabzählbarkeit der reellen Zahlen ist es uns nicht möglich diese durch die natürlichen Zahlen zu nummerieren. Das führt uns selbstverständlich zu einem kleinen Problem: wir haben unser Berechenbarkeitskonzept durch Registermaschinen nur auf den natürlichen Zahlen und durch Turingmaschinen auf den Wortfunktionen aufgebaut.

Was wir dagegen tun können, steht im nächsten Lernziel.

Lernziel 5

Definition berechenbarer Funktionen $f \subseteq {({\Sigma}^{\omega})}^k \rightarrow{\Sigma}^{\omega}$

Um was geht es hier? Um Funktionen, die mittels "real RAMs" berechnet werden können. Diese Maschinen haben, im Gegensatz zu unseren Registermaschinen auf natürlichen Zahlen, reelle Zahlen im Speicher.

Leider können wir sie physikalisch nicht realisieren (wir können keine reellen Zahlen in Registern speichern), da wir nur auf $1$ und $0$ arbeiten und die Menge der reellen Zahlen -wie wir oben gesehen haben- nicht nummerieren können. Was tun?

Kümmern wir uns zunächst um das Berechenbarkeitskonzept von Grzegorczyk und Lacombe aus 1955. Im Prinzip ist das nichts anderes als die Erweiterung unserer Turing-Maschine, so dass sie statt auf natürlichen Zahlen nun auf reellen arbeitet. Aber das geht doch nicht! Haben wir das nicht gerade gesagt? Doch, haben wir. Aber es gibt da eine Möglichkeit die Menge der reellen Zahlen doch zu nummerieren, so dass wir auf ihnen rechnen können.

Zunächst brauchen wir ein genügend großes Alphabet $\Sigma$. Dann werden mit $\Sigma^{\omega}$ unendliche Folgen definiert (im Gegensatz zum Skript, hätte ich hier direkt mit Cauchy angefangen... aber ist nun egal, welche als Namen für unsere reellen Zahlen dienen). Diese unendlichen Folgen sind unsere "Namen" für die reellen Zahlen.

Nachdem wir nun unsere Eingabewerte, die reellen Zahlen durch eine unendliche Folge von Symbolen über $\Sigma$ nummeriert haben haben, brauchen wir noch eine Maschine, die darauf rumrechnen kann.

Dazu nutzen wir eine sog. Typ-2-Maschine, wie sie im Skript genannt wird und definieren die Eingabebänder als unendlich (logisch, denn eine reelle Zahl in Dezimaldarstellung ist unendlich).

Auf diesen stehen dann die Namen der reellen Zahlen, eben Elemente aus der Menge $\Sigma^{\omega}$. Zu den $k$ Eingabebändern für unsere $k$ Worte hat die Maschine auch noch weitere, unendliche Arbeitsbänder, wie viele ist uns egal. Und natürlich besitzt sie auch ein Ausgabeband, wo am Ende die Ausgabe $q$ auftaucht, man diese jedoch nicht mehr verändern kann wenn man ein Zeichen der Ausgabe auf dem Band platziert hat (das ist eine wichtige Einschränkung, bitte merken!).

Wenn wir nun einen unendlichen Dezimalbruch z.B. durch 3 dividieren, werden in jedem Schritt eine Zahl der Eingabe gelesen und ggf. eine Zahl der Ausgabe geschrieben. Da die Berechnung unendlich ist, nähren wir uns so dem idealen Ergebnis (d.h. wir runden nicht) beliebig nah an.

Und diese Maschinen sind realisierbar! Das sin nämlich nichts anderes als unsere Computer.

Probleme bekommen wir, wenn wir multiplizieren wollen. Denn wenn wir als Eingabe z.B. $0,333334$ haben, so wurde auf das Eingabeband bereits eine $0,9...$ geschrieben. Wenn dann die $4$ hinter dem Komma zur Berechnung eingelesen wird, kann die Maschine auf dem Ausgabeband aber nicht mehr zurück um die (fälschlicherweise bereits geschriebene) $0,...$ durch eine $1,...$ ersetzen. Damit haben wir ein massives Problem.

Wir brauchen hier also unbedingt eine Lösung, denn ohne können wir z.B. nicht auf $\pi$ oder $e$ rechnen (wobei man $\pi$ auch anders approximieren kann). Um diese kümmern wir uns im nächsten Lernziel.

Antwort zum Lernziel: Wir definieren diese berechenbaren Funktionen über einer unendlichen Folge von Zeichen aus einem Alphabet $\Sigma$. Diese unendlichen Folgen dienen uns als Namen für die Elemente einer Menge, auf der wir tatsächlich rechnen wollen, aber mangels passender Darstellung nicht können!

Diese Funktion wird von einer Turingmaschine, einer sog. Typ-2-Maschine berechnet, die auf $k$ unendlichen Eingabebändern für die unendlichen Symbolfolgen unserer $k$ Eingabewerte rechnet und am Ende die Ausgabe auf ein unendliches Ausgabeband schreibt, auf dem die Schränkung gilt, dass man auf diesem nicht wieder nach links laufen und seine Ausgabe im Nachhinein korrigieren kann (Einweg-Ausgabe).

Lernziel 6

Definition der Cauchy-Darstellung der reellen Zahlen

Diese Berechenbarkeit können wir auf andere Mengen ausweiten wenn wir eine Funktion haben, die die Elemente dieser Menge quasi nummeriert, d. h. ihnen Namen gibt wie wir das mit $\Sigma^{\omega}$ getan haben.

Und genau das haben Grzegorczyk und Lacombe unabhängig von einander getan. Aber nicht mit einem Alphabet $\Sigma$, sondern mit sog. Cauchy-Folgen. Diese haben sie verwendet um die reellen Zahlen (aber Achtung: nicht alle reellen Zahlen sind effektiv berechenbar, aber dazu gleich mehr)  zu repräsentieren und umgingen so das oben angesprochene Problem mit der Multiplikation.

Die Typ-2-Maschine gibt bei der Eingabe einer nach $x$ konvergierenden Cauchy-Folge ebenfalls eine nach $f(x)$ konvergierende Cauchy-Folge aus.

Die Darstellung dieser Cauhy-Folge selbst ist wie folgt definiert:

$\rho:\subseteq\Sigma^{\omega}\rightarrow\mathbb{R}$:

$\rho(p)=x:\Leftrightarrow$ es gibt $u_0,u_1,...\in Def(\nu_{rat})$, so dass $p=u_0\#u_1\#...$, und $\forall k\in\mathbb{N}\mid x-\nu_{rat}(u_k)\mid\leq 2^{-k}$

Klopper! Macht nichts.

Zunächst: $\nu_{Du}$ ist die Darstellung (Dualnotation) der natürlichen Zahlen in Form von:

$\nu_{Du}(a_n...a_0):=\sum_{i=0}^n a_i 2^i$

Beispiel: $102$ in Dual ist $1100110$. Das, eingesetzt in die Formel ist: $0*2^0+1*2^1+1*2^2+0*2^3+0*2^4+1*2^5+1*2^6=102$.

Und damit ist $\nu_{Du}(1100110)=102$.

Ganz einfach. Ist also nichts weiter als die duale Darstellung einer natürlichen Zahl, bzw. die Nummerierung einer dualen.

$\nu_{rat}$ ist die (rationale) Darstellung der rationalen Zahlen in Form von:

$\nu_{rat}(u{c\!\!\!/}v):=\nu_{Du}(u)/\nu_{Du}(v)$.

Beispiel: $3\over{5}$ mit $11\over{101}$. Das, eingesetzt in die Formel bedeutet schlicht und ergreifend:

$\nu_{rat}(11{c\!\!\!/}101):=\nu_{Du}(11)/\nu_{Du}(101)=3/5$

Auch nicht viel schwerer. Nachdem wir das haben ist die Definition oben ein Stück deutlicher geworden.

Fragen wir uns zunächst, warum Cauchy?! Das Problem ist, dass diese Folge, auf der wir rumrechnen wollen eine Eigenschaft haben muss, die für uns unverzichtbar ist. Und zwar, dass sie schnell gegen unser gesuchtes $x$ konvergiert. Mit jedem Folgeglied kommen wir näher und näher an $x$ heran.

Suchen wir uns dazu eine Folge, die nicht schnell konvergiert, so haben wir nicht schnell genug Informationen zu unserem $x$, so dass wir evtl. in Probleme laufen, wie wir das mit der Multiplikation gesehen haben.

Aber Achtung, $\rho$ ist nicht injektiv, so dass es viele Cauchy-Darstellungen einer reellen Zahl $x$ gibt, d. h. jede reelle Zahl hat viele "$\rho$-Namen". Für uns ist nur wichtig, dass die gewählten Darstellungen das Cauchy-Kriterium erfüllen.

Dass es solche langsamen Folgen gibt, hat uns Hr. Specker in seinem Satz gesagt:

Es gibt eine wachsende, berechenbare Folge rationaler Zahlen, die nicht schnell konvergiert.

Wir brauchen also nicht nur eine Folge, sondern eine schnell konvergierende Folge. Und genau dazu ist das Cauchy-Kriterium da. Reden wir also zunächst über Cauchy bevor wir fortfahren.

Viele hatten das bereits in 1141, Grundlagen der Mathematik. Aber eine Wiederholung schadet sicher nicht:

$\forall\epsilon>0\exists n_0\in\mathbb{N}:\forall n,m>n_0:\mid a_{n}-a_{m}\mid<\epsilon$

Kommen da Erinnerungen hoch? Das bedeutet, dass für jedes $\epsilon$ ein Index $n_0$ existiert, so dass für alle anderen Indizes, die größer als $n_0$ sind gilt, dass der Abstand zwischen den Gliedern der Folge $a_n$ und $a_m$ kleiner ist als $\epsilon$. Die Glieder der Folge liegen also beliebig dicht. Das beliebig dicht ist das Zauberwort.

Sehr Ihr dieses hübsche $\epsilon$? Und nun schaut mal in die Definition unserer Cauchy-Darstellung: wir fordern dort, dass der Abstand zwischen unserem $x$ und einem Glied der Folge mit einer bestimmten Geschwindigkeit immer kleiner wird, eben unser $\epsilon$ mit $2^{-k}$. Das ist unsere Konvergenzgeschwindigkeit, die wir min. benötigen um genügend schnell genug Informationen zu unserem $x$ zu bekommen.

Die Cauchy-Darstellung einer Zahl $x$ ist also der "Name" dieser Zahl, die wir zum Rechnen benutzen. Die Glieder konvergieren so schnell gegen $x$, dass wir schon nach kurzer Zeit genug Informationen zu der Zahl haben, dass uns z.B. das Multiplikations-Problem von oben nicht passieren kann.

Und das ist auch der Satz von Prof. Weihrauch, der auch in der Literatur zitiert wird. Es geht aber nicht mehr um Zahlen, sondern um Funktionen auf reellen Zahlen:

Eine Funktion $f\subseteq\mathbb{R}\rightarrow\mathbb{R}$ ist berechenbar, wenn es eine Typ-2-Turingmaschine $M$ gibt, die jeden Namen von $x\in{Def(f)}$ (unsere Cauchy-Folge, die gegen $x$ konvergiert) in einen Namen von $f(x)$ (unsere Cauchy-Folge, die gegen $f(x)$ konvergiert) überführt.

Wir rechnen also ab jetzt auf Gliedern einer Folge und brauchen dazu eine Typ-2-Turingmaschine, die uns zu einer reellen Zahl $x$ eine Cauchy-Folge ausgibt, darauf herumreitet und uns die Cauchy-Folge zum Ergebnis $f(x)$ ausspuckt. Ich wiederhole mich, oder 😉

Dieser Satz ist im Skript auch in Prosa beschrieben:

Die reelle Funktion $f$ ist dann berechenbar wenn wir ein Verfahren angeben können, dass eine gegen $x$ aus der Definitionsmenge von $f$ konvergierende Folge (d.h. unser Name für $x$) in eine schnell gegen $f(x)$ konvergierende Folge überführt, die ein Name für unser Ergebnis ist.

Also genau das, was wir gerade bereits gesagt haben.

Man macht sich leicht klar, dass die Folgen nichts anderes sind als die (unendliche) Darstellung unseres Parameter, mit dem wir die Funktion füttern und unseres Ergebnisses. Sie können nie größer sein als das Ergebnis $f(x)$ oder der Parameter $x$ (die sind unsere Limes) und nähren sich diesen beliebig (unendlich) nah an. Und das auch noch so schnell, dass wir garantiert kein Falschergebnis bekommen wie z.B. bei bei der Multiplikation von oben.

Aber Moment mal: wir brauchen eine Typ-2-Turingmaschine, die uns eine Cauchy-Folge für eine reelle Zahl $x$ berechnet? Fällt euch jetzt schon das Problem auf? Wir haben nur eine abzählbare Anzahl an Turingmaschinen und damit auch eine abzählbare Anzahl an Typ-2-Maschinen. Aber eine überabzählbare Anzahl an reellen Zahlen. Was folgt daraus? Ein etwas beängstigender Satz:

Es gibt reelle Zahlen, die nicht berechenbar sind.

Diese berechenbaren Zahlen bilden also einen Teilkörper (in der Literatur wird er $EC$ - effectively computable - genannt) der reellen Zahlen.

Bleiben wir auf dem mathematischen Boden, so sind folgend einige Beispiele von reellen, berechenbaren Funktionen aus dem Skript:

• $f(x)=-x$
• $f(x,y)=x+y$
• $f(x,y)=max(x,y)$
• $f(x,y)=xy$
• $f(x)=1/x$
• $f(x)=\sqrt{x}$
• $f(x)=e^x$
• $f(x)=sin(x)$
• $f(x)=log(x)$

Wichtig: der fundamentale Stetigkeitssatz besagt, dass Stetigkeit eine notwendige Voraussetzung für $\rho$-Berechenbarkeit ist. Die Funktion darf also keine Sprungstellen haben. Eine Heaviside-Funktion (Sprungfunktion) ist damit also z.B. nicht $\rho$-berechenbar.

Antwort zum Lernziel: Um uns die Möglichkeit zu verschaffen mit reellen Zahlen zu rechnen, was wir offenbar tun und müssen, ist es notwendig diese in einer bestimmten Form darzustellen (da wir in Registern keine reellen Zahlen speichern können) und sie auf ein Berechenbarkeitsmodell zurückzuführen. Basis dieses Modell ist die bereits erwähnte Typ-2-Maschine.

Jedoch haben wir mit der Darstellung der reellen Zahlen als Dezimalzahlen ein Problem (siehe Multiplikation), dass wir nur lösen können wenn wir diese so codieren, ihnen also Namen geben, die uns die notwendigen Informationen der Dezimalstellen der reellen Zahlen so schnell wie möglich liefern.

Wir haben die Möglichkeit die reellen Zahlen als Folgen zu codieren, die gegen diese Zahlen konvergieren. Aber nicht als irgendwelche Folgen, sondern als Folgen mit einem bestimmten Geschwindigkeitskriterium: der Cauchy-Eigenschaft um uns so schnell wie möglich mit den notwendigen Informationen versorgen damit wir nicht in Probleme wie mit der Multiplikation laufen.

Dieses so schnell wie möglich wird mit dem Faktor $2^{-k}$ für jedes Glied der Folge spezifiziert, es bezeichnet den Abstand zwischen der abgebildeten, reellen Zahl $x$ und dem Glied der Folge $a_k$. Solange dieses Kriterium gilt, können wir uns mit $\rho$ eine beliebige Folgen-Darstellung einer reellen Zahl $x$ aussuchen. Denn durch die Nicht-injektivität von $\rho$ kann eine reelle Zahl $x$ mit mehreren Cauchy-Folgen dargestellt werden.

Lernziel 7

Zeigen, dass z.B. $x \mapsto x+5$ $(\rho,\rho)$-berechenbar ist

Was tun wir, wenn wir die Berechenbarkeit einer Funktion zeigen wollen? Wir verweisen auf die obigen Beispiele 😉 Und wenn wir dazu gezwungen werden, das selbst zu tun? Dann versuchen wir es doch:

Um zu zeigen, dass $f(x) = x+5 (\rho,\rho)$-berechenbar ist, müssen wir eine "Typ-2-Maschine" angeben, die als Eingabe das codierte Wort $p$, d.h. die Cauchyfolge $u_0\#u_1\#...$ (Eingabeparameter $x$) als Darstellung der reellen Eingabe $x$ annimmt und in eine Folge $q=\omega_0\#\omega_1\#...$ (reelles Ergebnis $f(x)$) umwandelt, so dass gilt:

$\rho(p)+5=\rho(q)$.

Die $5$ können wir auch mit auf das Eingabeband schreiben, getrennt durch $\#\#$ von $p$, der Folge für $x$.

Ebenfalls muss es möglich sein, die $5$ durch eine Cauchy-Folge $v_0\#...\#v_k$ zu codieren und dann $\nu_{rat}(\omega_k) = \nu_{rat}(u_k)+\nu_{rat}(v_k)$ ausgeben zu lassen. Aber ihr habt den Ansatz nachvollziehen können, hoffe ich.

Die gesuchte Maschine $M$ gibt dann die Worte $\omega_k$ aus, so dass $\nu_{rat}(\omega_k) = \nu_{rat}(u_k)+5$ gilt.

Um das Cauchy-Kriterium, die geforderte Konvergenzgeschwindigkeit $2^{-k}$ zu erfüllen, gilt:

$\mid x-\nu_{rat}(u_k)\mid\leq2^{-k}$

Wir wollen ja, dass die Glieder unserer Folge gegen der Eingabe gegen $x$ konvergieren.

$\mid (x+5)-\nu_{rat}(\omega_k)\mid\leq2^{-k}$

Und auch die Glieder der Folge unseres Ergebnisses sollen gegen das Ergebnis $f(x) = x+5$ konvergieren.

Damit ist $x \mapsto x+5$ $(\rho,\rho)$-berechenbar. Oder zumindest wäre das auf die Schnelle der Ansatz, den ich fahren würde.

Eventuell trage ich eine ausführliche Darstellung im Rahmen der Prüfungsvorbereitung hier nach.

Antwort zum Lernziel: Um zu zeigen, dass eine Funktion $f$ $\rho,\rho$-berechenbar ist, muss man die reellen Eingabeparameter mittels einer Folge codieren, deren Glieder $a_k$ das Cauchy-Kriterium mit der Konvergenzgeschwindigkeit $2^{-k}$ erfüllen. Das gilt ebenfalls für die Glieder der Ausgabe $f(x)$.

Erfüllen diese das Kriterium und ist die Funktion selbst berechenbar, so ist die Funktion $f$ ebenfalls $\rho,\rho$-berechenbar.

Wer Fehler findet (vor allem im letzten Abschnitt), ASAP in die Kommentare damit ich das schnell berichtigen kann.

Datum: 16. Mai 2013
Kategorie: Theoretische Informatik
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url