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

Update: auch diesen Beitrag habe ich auf die Lernziele gemünzt und ein paar Fehler behoben.

Bei dieser KE fühlt es sich leicht an wie ein kleiner Bruch. Es ist ein komplett neues Thema und so erschließt sich auf den ersten Seiten nicht unbedingt der Sinn dahinter. Zumindest mir nicht. Erst gegen Ende der Kurseinheit sieht man, wo die Reise hingegangen ist: zu der Berechenbarkeit der reellen Zahlen. Denn vorher haben wir nur die Berechenbarkeit von Wort- und Zahlenfunktionen betrachtet.

Ich werde daher immer ein Stück vorgreifen wenn ich denke, dass es dem Verständnis förderlich ist und mir nicht die Pointe für den Schluss aufheben.

Lernziel 1

Definition der Berechenbarkeitskonzepte, welche durch eien Nummerierung auf einer Menge $M$induziert werden: $\nu$-rekursiv, $\nu$-r.a, $(\nu,{\nu}^{'})$-berechenbar

Wir erinnern uns noch an die Churchsche These? Wenn nicht, bitte nochmal nachlesen. Wird hier noch einmal wichtig werden. Im Grunde geht es hier wieder um die Verschlüsselung von Elementen aus abzählbaren Mengen (hier sei nochmal erwähnt: eine Menge ist abzählbar wenn sie die gleiche Mächtigkeit wie $\mathbb{N}$ hat) durch Zahlen oder Wörter, da wir Zahlen mit Register- und Wörter mit Turingmaschinen berechnen können.

Wir erinnern uns auch an unsere Standardnummerierung $\nu_\Sigma$ oder die Nummerierung der einstelligen berechenbaren Zahlenfunktionen $\varphi$. Diese sind total (überall definiert) und sogar bijektiv (bis auf $\varphi$). Nun führen wir ein weiteres Berechenbarkeitskonzept ein, dass nicht weit weg von dem ist, was wir schon haben. Nehmen wir die Definition also Stück für Stück auseinander.

Es seien $\nu: \subseteq \mathbb{N} \rightarrow M$ und $\nu: \subseteq \mathbb{N} \rightarrow M_1$ Nummerierungen.

Eine Menge $X \subseteq M$ heißt $\nu$-rekursiv, gdw. es eine berechenbare Funktion $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}$ gibt mit:

$g(i)=\begin{cases}1&\text{falls } \nu(i) \in X \\0&\text{sonst }\end{cases}$

für alle $i \in Def(\nu)$.

Das ist das Äquivalent zu unserer Entscheidbarkeit/Rekursivität für Zahlen- und Wortfunktionen. Durch die Nummerierung $\nu$ nummerieren wir alle Elemente aus der Menge $M_1$ und die Funktion $g$ entscheidet für uns ob die gegebene Nummer eines Elements aus $M_1$ uns zu einem Element bringt, dass in der Menge $X$ liegt oder nicht.

Es geht uns also im Endeffekt nur darum die Elemente aus der Menge $X$ zu entscheiden.

Machen wir erst einmal weiter im Text. Anschließend folgt ein Beispiel um es etwas "greifbarer" zu machen.

Eine Menge $X \subseteq M$ heißt $\nu$-rekursiv-aufzählbar, gdw. es eine berechenbare Funktion $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}$ gibt mit:

$g(i)=\begin{cases}existiert&\text{falls } \nu(i) \in X \\div&\text{sonst }\end{cases}$

für alle $i \in Def(\nu)$.

Und hier haben wir das Äquivalent zu unserer Semi-Entscheidbarkeit/rekursiver Aufzählbarkeit.

Wir können zwar immer sagen, ob ein Element zu einer Menge $X$ gehört, haben aber bei der gegenteiligen Aussage ein Problem. Denn hier divergiert die Funktion, sie gibt uns also kein Ergebnis und kann unendlich laufen. Es ist also festgelegt, dass wir im positiven Fall (irgendwann) eine Antwort erhalten, im negativen Fall aber nicht. Prominente Beispiele für die Semi-Entscheidbarkeit sind - wie im verlinkten Beitrag erwähnt - das Halteproblem und der Busy Beaver.

Und nun die letzte Definition für diesen Abschnitt. Hier geht es nicht um eine Menge, sondern um eine Funktion:

Eine Funktion $f \subseteq M_1 \rightarrow M$ heißt $(\nu_1,\nu)$-berechenbar, gdw. es eine berechenbare Funktion $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}$ gibt mit:

$f \circ \nu_1(i) = \nu \circ g(i)$ für alle $i$ mit $\nu_1(i) \in Def(f)$.

Wenn man es ausklammert, hat man vielleicht einen besseren Blick auf die Funktion: $f(\nu_1(i)) = \nu(g(i))$ für alle $i$ mit $\nu_1(i)\in Def(f)$. Okay, das hat nicht unbedingt super geklappt. Diese definition bedeutet, dass eine Menge $(\nu_1,\nu)$-berechenbar ist wenn es ein Verfahren gibt, dass uns zu jeder $\nu_1$-Nummer eines Elements der Definitionsmenge von $f$ eine $\nu$-Nummer der Bildmenge von $f$ berechnet.

Während also die Funktion $f$ auf ihren Mengen (zu einem Definitionswert aus $M_1$ gibt es durch die Funktion einen Funktionswert aus $M$) herumrechnet, kümmern wir uns mit der Funktion $g$ um die Umrechnung der "Nummerierungsnummern" $\nu$ und $\nu_1$ der beiden Mengen $M_1$ und $M$.

Okay, das ist wahrscheinlich nicht sonderlich einleuchtend. Ich würde sagen, wir suchen uns ein nettes Beispiel.

Was wir zum Durchspielen der Definition brauchen sind

• zwei Nummerierungen $\nu$ und $\nu_1$,
• zwei Funktionen $f: \subseteq M_1 \rightarrow M$ (diese Funktion nimmt als Argument ein Element aus der Menge $M_1$ entgegen und gibt uns als Ergebnis ein Element aus der Menge $M$) und
• $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}$ (diese jedoch bekommt als Argument ein Element aus den natürlichen Zahlen $\mathbb{N}$ und gibt uns auch eins als Ergebnis zurück) und
• unsere beiden Mengen $M$ und $M_1$.

Fangen wir einfach mal mit dem Beispiel an und belegen wir unsere Mengen, Funktionen und Nummerierungen mit konkreten Werten:

• $M=\{2,4,6\}$: einfach willkürlich gewählt
• $M_1=\{1,2,3\}$: ebenfalls willkürlich
• $f \subseteq M_1 \rightarrow M: f(x) = 2x$. Willkürlich gewählt. Einzige Bedingung war, dass wir als Definition- und Bildwerte Elemente aus den Mengen $M_1$ und $M$ benutzen müssen. Also habe ich eine Funktion genommen, die Argumente aus $M_1$ auf Ergebnisse aus $M$ abbildet. Ihr könnt einfach mal andere Mengen wählen und die Funktion an diese anpassen. Das Ergebnis ist am Ende gleich.

Wenn wir die Funktion mit unseren Werten aus $M_1$ füttern, so bekommen wir: $f(1) = 2$, $f(2) = 4$ und $f(3) = 6$. Unsere Definitionsmenge $Def(f)$ ist also $\{1,2,3\}$ und entspricht wie gewünscht unserem $M_1$ (die Funktion $f$ ist hier sogar total, denn $Def(f) = M_1$, wie man sieht). Die Bildmenge, unsere Ergebniswerte der Funktion sind $Bild(f) = \{2,4,6\}$ und entsprechen also komplett unserer Menge $M$. Sie ist hier sogar surjektiv (auch rechtstotal genannt), denn $Bild(f) = M$ (jedes Element aus der Menge $M$ wird "getroffen"). Da wir auch noch injektiv (auch linkstotal genannt) sind, ist die Funktion bijektiv. Aber das nur nebenbei.

• $g: \subseteq \mathbb{N} \rightarrow \mathbb{N}: g(x) = 2x$. Diese Funktion muss $f \circ \nu_1(i) = \nu \circ g(i)$ für alle $i$ mit $\nu_1(i) \in Def(f)$ erfüllen. Der Kreis $\circ$ ist ja bekanntlich einfach nur eine Komposition. Es muss also gelten: $f (\nu_1(i)) = \nu(g(i))$. Testen wir das doch gleich mit konkreten Werten. Aber vorher müssen wir unsere Nummerierungen wählen:
• $\nu: \subseteq \mathbb{N} \rightarrow M$. Die Nummerierung von $M$ ist willkürlich gewählt, aber Hauptsache eindeutig und von $\nu_1$ verschieden. Wir nehmen einfach $-12$ für $\nu$, d.h. $\nu(14) = 2$, $\nu(16) = 4$ und $\nu(18) = 6$. Jetzt noch die Nummerierung der Elemente aus der Menge $M_1$.
• $\nu_1: \subseteq \mathbb{N} \rightarrow M_1$. Hier nehmen wir $-6$ für $\nu_1$, d.h. $\nu_1(7) = 1$, $\nu(8) = 2$ und $\nu(9) = 3$. Damit ist auch die Menge $M_1$ nummeriert.

Jetzt können wir mal schauen, ob unsere Funktion $g$ die Bedingung $f \circ \nu_1(i) = \nu \circ g(i)$ erfüllt und probieren alle unsere Werte aus den Mengen $M$ und $M_1$ mal aus:

$\begin{array}{lcl}f(\nu_1(7))&=&f(1)\\{}&=&2\end{array}$

Und nun $g$:

$\begin{array}{lcl}\nu(g(7))&=&\nu(14)\\{}&=&2\end{array}$

Damit ist $f \circ \nu_1(7) = \nu \circ g(7)$ erfüllt. Probiert das doch mal mit den restlichen Werten $8$ und $9$ aus.

Mit dem Beispiel können wir auch die beiden Grafiken nachvollziehen, die im Skript drin stehen (ich habe beide Diagramme ein Stück weiter unten als Textform inkl. Beispiel beschrieben). Diese durch $f \circ \nu_1(i) = \nu \circ g(i)$ induzierte Beziehung bringt uns zu dem im Skript beschriebenen Ausdruck: Das Diagramm kommutiert.

Eine Funktion $f: \subseteq M_1 \rightarrow M$ ist $(\nu_1,\nu)$-berechenbar wenn es ein Verfahren gibt, welches zu jeder $\nu_1$-Nummer eines Elementes $x \in Def(f)$ eine $\nu$-Nummer von $f(x)$ berechnet.

Am obigen Beispiel angelehnt bedeutet es nichts weiter, dass unsere Funktion $f$ dann $(\nu_1,\nu)$-berechenbar ist wenn wir ein Verfahren zeigen können, dass zu jeder $\nu_1$-Nummer (also $,7,8,9$) eines $x \in Def(f)$ (also $1,2,3$) eine $\nu$-Nummer (also $14,16,18$) von $f(x)$ (also $2,4,6$) berechnet. Um es nochmal in Deutsch zu formulieren: wir müssen ein Verfahren angeben, welches uns zu einer gegebenen Zahl $v_1$-Nummer eine $v$-Nummer ausgibt.

Wählen wir z.B. als $\nu_1$-Nummer wieder die $7$, so müssen wir am Ende eine $14$ als $\nu$-Nummer herausbekommen: $\nu_1(7) = 1, f(1) = 2, \nu(2) = 14$. Anhand der Definitionen können wir so einfach ein Verfahren herleiten: $(2(i-6))+12 = 2i$. Damit bekommen wir zu jeder gegebenen $\nu_1$ eines $x \in Def(f)$ die zugehörige $\nu$-Nummer von $f(x)$. Das haben wir in dem Beispiel getan und gezeigt, dass unsere Funktion $f$ $(\nu_1,\nu)$-berechenbar ist.

Diese beiden Vierecke aus dem Skript sehen in Linie dargestellt wie folgt (inkl. Beispiel) aus:

Diagramm: $\mathbb{N}\rightarrow (g)\rightarrow \mathbb{N}\rightarrow (\nu)\rightarrow{M}\leftarrow (f)\leftarrow M_1\leftarrow (\nu_1)\leftarrow \mathbb{N}$

Beispiel: ${7}\rightarrow g(7)\rightarrow 14\rightarrow \nu(14)\rightarrow{2}\leftarrow f(1)\leftarrow 1\leftarrow \nu_1(7)\leftarrow 7$

Diagramm: $i\rightarrow (g)\rightarrow g(i)\rightarrow (\nu)\rightarrow{f(x)}\leftarrow (f)\leftarrow x\leftarrow (\nu_1)\leftarrow i$

Beispiel: $7\rightarrow g(7)\rightarrow 14\rightarrow \nu(14)\rightarrow{2}\leftarrow f(1)\leftarrow 1\leftarrow \nu_1(7)\leftarrow 7$

Beachtet hier bitte die Einschränkung aus dem Skript. Die Funktion $g$ arbeitet nur vernünftig für alle $i$ mit $\nu_1(i) \in Def(f)$. D.h. Das Ergebnis von $\nu_1(i)$ muss im Definitionsbereich unserer Funktion $f$ liegen. Dieser ist wie wir oben gesehen haben ja $Def(f) = M_1$ und $M_1=\{1,2,3\}$. Also muss das Ergebnis von $\nu_1(i)$ $1,2$ oder $3$ sein. Und das geht nur wenn $i \in \{7,8,9\}$ ist. Für alle anderen Werte für $i$ geht das natürlich nicht.

Antwort zum Lernziel: In den vergangenen Kurseinheiten haben wir uns um die Berechenbarkeit auf Zahlen- und Wortfunktionen gekümmert. In dieser Kurseinheit interessieren wir uns auf die Berechenbarkeitsmodelle auf beliebigen Mengen.

Um jedoch eine Berechenbarkeit auf diesen beliebigen Mengen zu induzieren, denn wir können mittels Register- und Turingmaschinen nur auf Zahlen oder Worten rechnen, brauchen wir Nummerierungen dieser Elemente und angepasste charakteristische Funktionen um unsere Definition für Rekursivität und rekursive Aufzählbarkeit auf diese Mengen zu übertragen.

Wir sind auch nicht nur auf eine einzige Nummerierung beschränkt, die uns Definitions- und Wertemenge nummeriert. Durch eine "Übersetzungsfunktionen" können wir diese Nummerierungen ineinander "überführen" und es uns so ermöglichen auf den unterschiedlichen Nummerierungen zweier Mengen rechnen zu können.

Lernziel 2

Nachweis der $\nu$-Rekursivität und $(\nu,{\nu}^{'})$-Berechenbarkeit

Nun haben wie die $\nu$-Rekursivität, -rekursive-Aufzählbarkeit und $(\nu,{\nu}^{'})$-Berechenbarkeit definiert, jetzt wollen wir auch etwas mit unserem Wissen anstellen.

Wollen wir doch mal versuchen das für zwei Beispiele aus dem Skript nachzuweisen.

Aufgabe 1: Nachweis der $(id_{\mathbb{N}},\nu)$-Berechenbarkeit einer Nummerierung $\nu: \subseteq \mathbb{N} \rightarrow M$.

Wir machen uns wieder klar, was wir hier zeigen müssen. Wir müssen zeigen, dass es ein Verfahren gibt, welches zu jeder $id_{\mathbb{N}}$-Nummer eines Elementes $x\in Def(\nu)$ eine $\nu$-Nummer von $\nu(x)$ berechnet. Etwas verwirrend, da die Definition noch ein $f$ verlangt, aber das $f$ ist in diesem Fall einfach nur die Nummerierung $\nu$.

Formal ausgedrückt:

$\nu \circ id_{\mathbb{N}}(i) = \nu \circ g(i)$ für alle $i$ mit $id_{\mathbb{N}}(i) \in Def(\nu)$

(nochmal zur Erinnerung $id_{\mathbb{N}}(k) = k$ für alle $k \in \mathbb{N}$, d.h. $id_{\mathbb{N}}(5) = 5$)

Wir suchen also ein $g$, dass die obige Gleichung erfüllt. Wenn Ihr die Komposition klammert sehr Ihr vielleicht auch schon, was für ein $g$ wir suchen:

$\nu (id_{\mathbb{N}}(i)) = \nu(g(i))$ für alle $i$ mit $id_{\mathbb{N}}(i) \in Def(\nu)$

Schon erkannt, was für ein $g$ wir suchen? Wir wählen als Beispiel wieder unsere Nummerierung $\nu$ von oben ($\nu(14) = 2, \nu(16) = 4,\nu(18) = 6$) und haben bei z.B. $i = 14$ folgende Gleichung (zunächst die linke Seite):

$\begin{array}{lcl}\nu (id_{\mathbb{N}}(14))&=&\nu(14)\\{}&=&2\end{array}$

Wir brauchen die Gleichung hier nur aufzulösen:

Wir müssen also $\nu(g(14)) = 2$ setzen. Was nummeriert mit der $2$ unser $\nu(?)=2$? Genau! Die $14$ wird durch $\nu$ mit der $2$ nummeriert (siehe oben): $\nu(14)=2$. Daher muss unser $g$ die $1$ auf die $14$ abbilden: $g(14)=14$ um die Gleichung zu erfüllen.

Aber jetzt habt Ihr sicher schon gemerkt, welches $g$ wir suchen.

Wir wählen $g=id_{\mathbb{N}}$ und rechnen die rechte Seite aus:

$\begin{array}{lcl}\nu (id_{\mathbb{N}}(14))&=&\nu(g(14))\\{}&=&\nu(14)\\{}&=&2\end{array}$

Passt! Damit ist unser $g$ richtig gefunden und es gilt:

$\nu (id_{\mathbb{N}}(i)) = \nu(id_{\mathbb{N}}(i))$

Die Nummerierung  $\nu: \subseteq \mathbb{N} \rightarrow M$ ist damit $(id_{\mathbb{N}},\nu)$-berechenbar.

Aufgabe 2: zeigen, dass $\mathbb{Z}^+ := \{z\in\mathbb{Z} \mid z > 0\}$ $\nu_{\mathbb{Z}}$-rekursiv ist

Wir schauen nochmal nach oben auf die Definition der $\nu$-Rekursivität und sehen, dass wir eine Funktion $g$ angeben müssen, die für alle $i \in Def(\nu_{\mathbb{Z}})$ entscheidet ob das Element in $\mathbb{Z}^+$ liegt oder nicht.

Die Definition von $\nu_{\mathbb{Z}}$ ist: $\nu_{\mathbb{Z}} : \mathbb{N} \rightarrow \mathbb{Z}$, $\nu_{\mathbb{Z}}<i,j> := i-j$ $\forall i,j \in \mathbb{N}$.

Noch nicht so ganz klar? Kein Problem: schaut euch nochmal den Beitrag zur Cantorschen Tupelfunktion an, insbesondere die Inverse dazu.

Es gilt $\nu_\mathbb{Z}(500)=<27,4>$. Da $(i-j)>0$ gilt, gilt auch $i>j$. Wir geben nun unsere Funktion $g$ an:

$g<i,j>=\begin{cases}1&\text{falls } i > j \\0&\text{sonst }\end{cases}$

Die Funktion ist berechenbar (Ihr könnt ja mal eine Registermaschine angeben, die sie berechnet) und für alle $k \in \mathbb{N}$ gilt: $\nu_\mathbb{Z}(k) > 0\Longleftrightarrow g(k) = 1$. Die Menge ist also $\nu_\mathbb{Z}$-rekursiv.

Damit hätten wir schon fast die Hälfte abgehakt. Ich hoffe es war alles verständlich. Beitrag 2/2 folgt alsbald.

Und wieder ganz wichtig: wer Fehler findet, bitte sofort in die Kommentare damit niemand auf eine ungenaue Fährte gelockt wird.

Antwort zum Lernziel: Für den Nachweis der $\nu$-Rekursivität einer Menge $X$ muss man eine volle charakteristische Funktion $g$ angeben, die zu der Nummerierung $i$ angibt ob das nummerierte Element $\nu(i)$ in der Menge $X$ liegt oder nicht. Der Nachweis der rekursiven Aufzählbarkeit gelingt durch die "halbe" charakteristische Funktion.

Für den Nachweis der Berechenbarkeit benötigen wir ein Verfahren, eine Funktion $g$, dass uns die unterschiedlichen Nummerierungen der beiden Mengen "umrechnet", auf denen die Funktion $f$ eigentlich rechnet (ihre Definitions- und Wertemenge).

Noch ein paar wichtige Definitionen außerhalb der Lernziele, aber nicht weniger wichtig:

Eine weitere, naheliegende Eigenschaft der Nummerierungenen ist auch ihre Transitivität:

Sei $f\subseteq M_1\rightarrow M_2$ $(\nu_1,\nu_2)$-berechenbar und $g\subseteq M_2\rightarrow M_3$ $(\nu_2,\nu_3)$-berechenbar, so ist die Komposition von $g$ und $f$ $g\circ f$ $(\nu_1,\nu_3)$-berechenbar.

Konnte man sich schon fast denken. Braucht sicherlich nicht viele Erklärungen. Man kann direkt sehen, dass wir die Menge $M_2$ als Bindeglied zwischen $f$ und $g$ durch ihre Nummerierung $\nu_2$ haben.

Und nun noch etwas zur Notation:

Eine Notation der Menge $M$ ist eine ggf. partielle, surjektive Funktion $\nu:\subseteq\Sigma^{*}\rightarrow{M}$, wobei $\Sigma$ ein Alphabet ist.

Leuchtet ein. Wir können die Menge $M$ nicht nur nummerieren, wie wir das vorher getan haben und mit Registermaschinen berechnen, sondern wir können diese Menge auch mit Worten über einem Alphabet $\Sigma$ "nummerieren". Nur nennt man das nicht mehr eine Nummerierung, sondern eine Notation!

Weiter geht es im folgenden Beitrag.

Buchempfehlung

Datum: 15. April 2013
Kategorie: Theoretische Informatik
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url