TIA: Berechenbare Zahlenfunktionen (Lernziele KE2)

In dieser Kurseinheit gibt es zwar nicht viele Lernziele, aber lasst euch nicht täuschen: sie sind wichtig. Die Beiträge zu diesem Thema, die ich auch im passenden Kontext in diesem Beitrag verlinkt habe sind:

Starten wir aber einfach wieder anhand der Lernziele und kämpfen uns da durch.

Lernziel 1

Angabe und Erläuterung der Definition und der Eigenschaften der Cantorschen Tupelfunktion

Zum Glück habe ich bereits hier einen langen Beitrag zum Thema erstellt und wiederhole mich deswegen nicht, sondern springe sofort zur Antwort.

Antwort zum Lernziel: mit der Cantorschen Tupelfunktion ist es uns möglich einem n-Tupel mit Elementen aus \mathbb{N} eine einzige, eindeutige Zahl aus \mathbb{N} zuzuordnen (Reduktion). Durch diese bijektive Abbildung von \mathbb{N}^n\rightarrow\mathbb{N} können wir uns auf die Berechnung von einstelligen Funktionen beschränken.

Einen weiteren prominenten Platz hat die Cantorsche Tupelfunktion bei dem Vergleich von Mengen: zwei Mengen sind gleichmächtig wenn man zwischen ihnen eine Bijektion herstellen kann.

Lernziel 2

Erläuterung der Abschlusseigenschaften berechenbarer Zahlenfunktionen

Ich bin mir hier gerade etwas unschlüssig: im Skript ist nicht mehr viel zu dem Thema drin, als der Satz zur Substitution, primitive Rekursion, \tilde{\mu} und der Umkehrfunktion. Vielleicht dann am besten an ein paar Beispielen?

Substitution

Zunächst haben wir zwei ggf. partielle Funktionen g:\subseteq\mathbb{N}^m\rightarrow\mathbb{N} und ggf. partielle Funktionen h_1 bis h_m (d.h. so viele Funktionen wie der Definitionsbereich von g Parameter hat), mit h_1,...,h_m\subseteq\mathbb{N}^k\rightarrow\mathbb{N}. Alle Funktionen sind berechenbar. Dann ist auch die Substitution Sub(g,h_1,...,h_m) berechenbar.

Sub(g,h_1,...,h_m)\subseteq\mathbb{N}^k\rightarrow\mathbb{N} ist definiert durch Sub(g,h_1,...,h_m)(x):=g(h_1(x),...,h_m(x))

Viel Zeug, oder? Keine Sorge, ist ganz easy.

Beispiel

g(x,y)=x+y

h_1(x,y,z)=x+y

h_2(x,y,z)=x+z

Die Substitution sieht nun so aus:

Sub(g,h_1,h_2)(x,y,z)=g(h_1(x,y,z),h_2(x,y,z)).

Belegen wir unsere Funktion mit Werten: x=2,y=3,z=4

\begin{array}Sub(g,h_1,h_2)(2,3,4)&=g(h_1(2,3,4),h_2(2,3,4))\\&=g(5,h_2(2,3,4))\\&=g(5,6)\\&=11\end{array}

War doch trivial, oder (das wollte ich immer schon mal sagen!)?

Primitive Rekursion

Das ist ein klein wenig ekeliger als die Substitution, aber wir bekommen das gleich noch klein.

Auch hier haben wir zwei Funktionen  g:\mathbb{N}^k\rightarrow\mathbb{N} und  h:\mathbb{N}^{k+2}\rightarrow\mathbb{N}, die berechenbar sind (Achtung: sie müssen auch total sein, denn sonst können wir nicht über diese "rekursivieren"). Wenn das der Fall ist, dann ist auch Prk(g,h) berechenbar.

Prk(g,h) ist definiert als:

f(x,0) = g(x)

f(x,y+1)=h(x,y,f(x,y))

Für alle x\in\mathbb{N}^k und y\in\mathbb{N}. Man sieht bereits jetzt, dass wir rekursiv arbeiten. Noch deutlicher wird es an einem Beispiel.

Beispiel

g(x,z)=x+z

h(a,b,x,z)=a+b+x+z

Nehmen wir einfach mal y=3 (3-malige Rekursion) und x=2,z=3,a=4,b=5.

\begin{array}Prk(g,h)(2,3)&=f(2,3,3)\\&=h(2,3,2,f(2,3,2))\\&=h(2,3,2,(h(2,3,1,f(2,3,1))))\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,f(2,3,0))))))\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,g(2,3))))))\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,5)))))\\&=h(2,3,2,(h(2,3,1,10)))\\&=h(2,3,2,16)\\&=23\end{array}

Versuchen wir das mit y=2:

\begin{array}Prk(g,h)(2,2)&=f(2,3,2)\\&=h(2,3,1,f(2,3,1))\\&=h(2,3,1,(h(2,3,0,f(2,3,0))))\\&=h(2,3,1,(h(2,3,0,5)))\\&=h(2,3,1,10)\\&=16\end{array}

Viel Text, aber sicherlich gut nachzuvollziehen. Wir loopen und also durch die Funktionen mit einer festen Anzahl an Schleifen! In diesem Beitrag habe ich die primitive Rekursion etwas detaillierter betrachtet.

Und was ist wenn wir keine feste Anzahl an Schleifen haben können? Dann hilft uns unser \mu-Operator.

\tilde{\mu}

Ist h mit h:\subseteq\mathbb{N}^{k+1}\rightarrow\mathbb{N} berechenbar, so ist es auch \tilde{\mu}(h). Wie ihr seht, auch hier ist h total. Was ist \tilde{\mu}?! \tilde{\mu}:\subseteq\mathbb{N}^{k}\rightarrow\mathbb{N}. Es ist definiert durch:

\tilde{\mu}(h)(x)=\mu y[h(x,y)=0]

What the... Entspannung, Entspannung! Das ist nichts weiter als unsere \mu-Rekursion. Ich suche gerade im Skript ob wir das bereits irgendwo auf den vorherigen Seiten hatten... witzig. Hatten wir nicht. Das ist wirklich die erste Erwähnung. Und dann gleich ins kalte Wasser. Nicht schlimm, denn unser \tilde{\mu} ist nichts weiter, als der Operator, der es uns erlaubt auch Dinge zu berechnen, wo wir die genaue Anzahl an Schleifendurchläufen noch nicht wissen.

Und zwar indem wir unserer zu berechnende Funktion so weit umformen, dass wir beim Ende der Berechnung auf eine Nullstelle stoßen. Ich werde das nicht groß ausführen, sondern verweise ganz frech auf meinen alten Beitrag zum Thema.

Umkehrfunktion f^{-1}

Das schwerste zum Schluss. Hier gehen wir davon aus, dass f injektiv ist (wichtig!). Wir beschränken uns auch auf einstellige Funktionen. Warum? Na? Na? Genau: aufgrund der Cantorschen Tupelfunktion können wir das. Wenn diese Funktion also berechenbar ist, so ist es auch ihre Umkehrfunktion. Klingt logisch. Ist es auch.

Während für f Totalität und Injektivität gefordert ist, können wir bei f^{-1} bei einer ggf. partiellen Funktion rauskommen. Das liegt daran, dass wir in der Bildmenge von f evtl. Elemente haben, die wir mit unserer Funktion nicht "treffen". Diese landen aber für f^{-1} dennoch in der Definitionmenge, sind aber nicht definiert. Damit ist f^{-1} eben partiell.

Beispiel

f(x) = x+5 mit der Umkehrfunktion f^{-1}(\tilde{x})=\tilde{x}-5. Setzen wir x=10 und \tilde{x}=f(x), so haben wir:

f(10)=15

f^{-1}(15)=10

Passt.

Damit haben wir die Abschlusseigenschaften für berechenbare Zahlenfunktionen durch.

Antwort zum Lernziel: Funktionen, die sich aus den Funktionen Substitution, primitive Rekursion, \mu-Rekursion und der inversen Funktion zusammensetzen sind ebenfalls berechenbar.

Für die Substitution können die Funktionen auch partiell sein, für de primitive und \mu-Rekursion sind wir jedoch auf totale Funktionen angewiesen, da wir sonst nicht durch die Schleifendurchläufe kommen. Während wir bei der primitiven Rekursion zwingend die Anzahl der Schleifendurchläufe kennen müssen, ist es uns bei der \mu-Rekursion durch das "Nullsetzen" der Funktion nicht wichtig. Es bricht eben ab wenn die Nullstelle gefunden ist. Wie lange es dauert wissen wir nicht.

Ersteres ist das Äquivalent zur LOOP-Schleife ("tue etwas genau x Mal"), während die \mu-rekursion einer WHILE-Schleife ("tue etwas bis...") entspricht.

Für die inverse Funktion benötigen wir neben einer totalen Funktion f jedoch auch die Eigenschaft der Injektivität für f, da wir nur auf maximal ein Element aus der Bildmenge abbilden dürfen, da sonst die Umkehrabbildung auf zwei unterschiedliche Elemente abbilden würde.

Lernziel 3

Definition der WHILE-Programme, Erläuterung ihrer Semantik und Angabe des Zusammenhangs zu berechenbaren Funktionen

Letztes Lernziel in dieser Kurseinheit. In diesem Beitrag sind die Details bereits herausgearbeitet, ich kümmere mich daher nur um die Definition und Semantik aus dem Skript. Das Fazit kann man wortwörtlich eig. auch für die Antwort zum Lernziel übernehmen. Also kümmern wir uns um die Syntax und die Semantik.

R_i+ und R_i- sind WHILE-Programme

Dabei addiert R_i+ im i-ten Registereine 1R_i- subtrahiert eine 1 im i-ten Register.

IF R_i=0 THEN P ELSE Q

Wir gehen davon aus, dass P und Q selbst WHILE-Programme sind.

WHILE R_i\neq 0 DO P

Kennen wir auch schon. Solange das Register R_i nicht 0 ist, wird P ausgeführt.

Zusätzlich dazu haben wir noch unser kleines Tau \tau. Dadurch weisen wir unseren oben beschriebenen Kommandos tatsächliche Funktionen auf der Datenmenge D=\mathbb{N}^{\mathbb{N}} zu, die wir bereits verbal beschrieben haben (sie ist die uns bekannte Datenmenge der Registermaschinen). Als Beispiel nehmen wir R_i+ und R_i-:

\tau(R_i+)(a_0,a_1,...):=(a_0,a_1,...,a_i+1,...,)

\tau(R_i-)(a_0,a_1,...):=(a_0,a_1,...,a_i-1,...,)

Wir können einem kompletten WHILE-Programm mittels \tau ebenfalls eine Ausgabe auf der Datenmenge D beschaffen: \tau(P). Und damit haben wir dann die komplette Registerausgabe unserer Maschine, die das Programm P berechnet. Damit schaffen wir es, dass unser Programm auf der Eingabecodierung einer Registermaschine operieren kann und uns auch eine Ausgabecodierung der Registermaschine liefert (siehe vorheriger Beitrag).

Noch eine kleine Definition für die WHILE-Berechenbarkeit

Wir nennen eine Funktion f:\mathbb{N}^k\rightarrow\mathbb{N} WHILE-berechenbar genau dann wenn gilt: f=AC(\tau(P)(EC))

Ähnliches Spiel wie im Beitrag zu KE1. Wir haben unterschiedliche Datenmengen für \tau und für die Flussdiagramme der Registermaschinen. Mit EC und AC wandelt wir diese nur ineinander um.

Das führt uns direkt zum Zusammenhang zu den berechenbaren Funktionen.

Beispiel

Funktion f(x,y)=x+y (operiert auf \mathbb{N}^2\rightarrow\mathbb{N})

Dazu haben wir ein WHILE-Programm P, welches uns die Funktion f berechnet. Es operiert auf \mathbb{N}^3\rightarrow\mathbb{N}^3

R0=R1;
WHILE R2 NOT 0 DO
  R0+;
  R2-;
END;

Wir können auch ein Flussdiagramm F einer Registermaschine M angeben, dass uns die gleiche Funktion raushaut.

Während das Flussdiagramm ebenfalls auf \mathbb{N}^3\rightarrow\mathbb{N}^3 operiert, haben wir bei der Registermaschine jedoch \mathbb{N}^3\rightarrow\mathbb{N}.

while-machine

Damit gilt f=\tau(P)=f_M=f_F. Oder doch nicht? Spielen wir das doch einfach mal mit x=2,y=3 durch:

f(2,3)=5

\tau(P)(0,2,3)=(5,2,0)

f_M(0,2,3)=5

f_F(0,2,3)=(5,2,0)

Okay, die Berechnung ist anscheinend in Ordnung. Aber die Ausgabe von z.B. \tau(P)(0,2,3)=(5,2,0) ist sicher nicht gleich f_M(0,2,3)=5 (siehe die Definition der Eingabe- und Ausgabecodierung von Registermaschinen im Lernziel 4 von Beitrag zu KE1).

Hier kommen unsere Funktionen EC und AC bei allen drei Berechnungsarten ins Spiel, die unsere Eingabe und unsere Ausgabe entsprechend umformen, so dass sie passen.

Definieren wir also z.B. AC für \tau(P) neu: AC(x,y,z)=x, so haben wir

\begin{array}{}AC(\tau(P)(0,2,3))&=AC(5,2,0)\\&=5\end{array}

Damit würde f_M=AC(\tau(P)) wieder passen.

Das spannende also daran ist, dass es durchaus vorkommen kann, dass unser Flussdiagramm, unsere Registermaschine oder unser WHILE-Programm nicht alle auf einer Datenmenge operieren, sondern alle auf unterschiedlichen Mengen (warum auch immer). Um aber zu sagen, dass z.B. \tau(P)=f_M gilt, müssen wir sie evtl. umgestalten. Für \tau(P)=f_F brauchen wir das hingegen - wie wir oben gesehen haben - nicht.

Lange Rede, kurzer Sinn:

Zu jedem WHILE-Programm gibt es ein Flussdiagramm einer Registermaschine mit \tau(P)=f_F

Zu jedem Flussdiagramm einer Registermaschine gibt es ein WHILE-Programm mit f_F=\tau(P) mit einer WHILE-Schleife.

Damit gilt: die Funktion f ist WHILE-berechenbar genau dann wenn sie Register-berechenbar ist.

Antwort zum Lernziel: die WHILE-Programme bestehen aus bedingten Anweisungen (IF) und Schleifen (WHILE), sowie Anweisungen zum Register hoch- oder runterzählen und Hintereinanderausführungen von Anweisungen.

Der Zusammenhang zu berechenbaren Funktionen kommt daher, dass man zu jedem WHILE-Programm eine Registermaschine angeben kann, die die selbe Funktion berechnet und zu jeder Registermaschine ein WHILE-Programm existiert.

WHILE-Programme sind mächtiger als LOOP-Programme: man kann LOOP-Schleifen mit WHILE-Schleifen nachbilden, aber nicht anders herum, da man die Anzahl der Schleifendurchläufe im Vorfeld nicht bei jeder WHILE-Schleife kennt.

Die LOOP-Anwendungen sind das Äquivalent zur primitiven Rekursion, während die WHILE-Programme erst mit dem \mu-Operator (durch "Nullsetzen" der Funktion) nachgebildet werden können.


Sie können zum Ende springen und ein Kommentar hinterlassen. Pingen ist im Augenblick nicht erlaubt.





 

3 Kommentare zu “TIA: Berechenbare Zahlenfunktionen (Lernziele KE2)”

  1. Mike
    September 15th, 2013 23:17
    1

    Hallo Anton,

    Du schreibst ganz richtig, dass die Umkehrfunktion (aus der Mathematik) nur berechenbar ist, wenn die Funktion injektiv ist. Auch die Anwendung auf die (bijektive) Cantorsche Tupelfunktion ist soweit so gut ..

    Nun kommt die Funktion f hoch -1 an diversen Stellen im Skript vor, aber selten im Zusammenhang mit injektiven Funktionen. Schnell in die Definitionen geschaut unter 1.3.1. Da ist von 'Umkehrkorrespondenz' die Rede und in KE 6 bei den Reduktionsbeweisen und Komplemente von totalen Funktionen ist das 'Urbild' gemeint. Aber nirgendwo in den Skripten taucht das Wort 'Umkehrfunktion' auf. Das Wort würde an den genannten Stellen auch keinen Sinn machen, wie mir auf den Studientagen während eines Vortrags von kompetenter Seite versichert wurde 🙂

    Viele Grüße
    Mike

  2. Anton
    September 15th, 2013 23:22
    2

    Hallo Mike,

    ich kann noch nicht ganz folgen. Wenn Du mich mal anmailst, wäre das nett. Ich würde deine Einwände gerne einpflegen.

    Gruß
    Anton

  3. Mike
    September 16th, 2013 09:25
    3

    Hallo Anton,

    wo finde ich Deine Emailadresse? Gerne kannst Du auch mir schreiben.

    Gruß
    Mike

Beitrag kommentieren