date-created: 2024-06-25 12:27:20 date-modified: 2024-06-25 01:03:43

Rekursive Funktionen

anchored to 112.00_anchor_overview proceeds from 112.21_rekursive_funktionen also from 112.20_turing_aequivalence

Overview

Wir haben zuvor die Berechnungsmodelle der while und goto Programme kennengelernt, welche wir als Turing-äquivalent bewiesen haben. Ferner haben wir auch gesehen, dass $for$ selbst strikt begrenzt ist!

Wir haben bis dato aber nur endliche Schleifen bei $for-loop$s betrachtet und somit eine relativ einfach Limitierung festgelegt.

Warum brauchen wir dann überhaupt unendliche Schleifen, bzw. die Möglichkeit einer TM nicht zu halten? Wir können ja einfach anch gewisser Zeit aufhören und somit das Halteproblem verhindern

Gibt es nicht-triviale Funktionen, die nicht mit $for$ berechenbar sind?!

Review | Hilberts Programm

[!Tip] Finitismus, zweites Problem von Hilbert

Frage: Sind die arithmetischen Axiome widerspruchsfrei?

Um Widersprüche zu vermeiden: Lässt sich mit finiten Methoden - also einem Formalismus, der nur endliche Mengen verwendet - die Widerspruchsfreiheit der Mathematik beweisen?

Diese Frage zielt spezifisch auf Russels Paradox ab, weil bei diesem erkennbar war, dass es einen Widerspruch in seiner Struktur erzeug(en)t kann.

Dafür wurde versucht das Ganze mit rekursiven Funktionen finit zu formalisieren.

–> historisch sind wurden sie etwas vor Turingmaschinen konzipiert ( man hat aber später den Bogen zwischen beiden gespannt und kann einsehen, dass die gleich sind bzw das gleiche Problem haben)

[!Attention] Was wir herausfinden werden

Wir werden sehen, dass rekursive Funktionen, ähnlich wie eine FA oder $for$ beschränkt sind!. –> Es gibt Funktionen, die nicht rekursiv berechenbar sind!

Dafür muss man zuerst Funktionen ähnlich zu Turingmaschinen “offen / transfinit” abschließen und die entsprechende Definition tätigen

Rekursive Funktionen

[!Req] $k$-stellige Funktionen

Wir werden folgende Funktionen betrachten: $$f:{\mathbb{N}}^k\to \mathbb{N}$$ die wir als $k$-stellige Funktionen bezeichnen

hierbei ist $\mathbb{N}$ immer $0$!

(Kontext: Rozsa Peter (1905, Budapest - 1977) wurde in Ungarn vor WWWII geborgen, war Jüdin, Frau und somit durch die Situation stark während des Krieges und den Umständen beeinträchtigt. Dennoch hat sie viel in der Mathematik umgesetzt #feminism !)

[!Definition] rekursve Funktionen

Die Menge der primitiv rekursiven Funktionen wollen wir folgend induktiv definieren:

wir benötigen hierfür 5 Pfeiler, welche wir definieren und dadurch rekursive Funktionen beschreiben wollen:

Welche funf Punkte definieren wir? #card

1. Die Konstante Funktion ($0$-stellige) $O:x⟼0$ ist primitv rekursiv

2. Die peano’sche Nachfolgerfunktion $s:\mathbb{N}\to \mathbb{N}$ mit $s(k)=k+1$ ist primitiv rekursiv ( kann die natürlichen Zahlen auflisten!)

3. Die Projektionsfunktion $f_i:{\mathbb{N}}^k\to \mathbb{N}$, $(x_1,x_2,\dots ,x_k)\mapsto x_i$ ist ebenfalls primitiv rekursiv ( die, die zu einem Tupel von Zahlen, dann den Nachfolger zurückgibt)

4. Die Komposition der primitiven Funktione ist weiterhin auch primitiv rekursiv! Seien $f:{\mathbb{N}}^k\to \mathbb{N}$ und ferner $g_1,\dots ,g_k:{\mathbb{N}}^m\to \mathbb{N}$ primitiv rekursive Funktionen, dann sind es auch die Komposition: $$h(x_1,\dots ,x_m)=f(g_1(x_1,\dots ,x_m),\dots ,g_k(x_1,\dots ,x_m))$$

5. Primitive Rekursion als Konstrukt werden auch primitiv rekursiv sein. Seien $g:{\mathbb{N}}^k\to \mathbb{N}$ und $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$ sind auch primitive rekursiv.

Dann ist folgend auch die Funktion $$p(g,h)=f$$ primitiv rekursiv ist. Mit der $k+1$ stelligen Funktion $f:{\mathbb{N}}^{k+1}\to \mathbb{N}$ erhalten wir dann zwei folgende Aussagen: $$\begin{array}{rl}>f(0,x_1,\dots ,x_k)& :=g(x_1,\dots ,x_k)\\ >f(s(n),x_1,\dots ,x_k)& :=h(f(n,x_1,\dots ,x_k),n,x_1,\dots ,x_k)>\end{array}$$ ( In der Struktur )

Die Mu-Funktion ist in der Idee gleich der While-Schleife und genau der Turing-Maschine. Die Idee: Wir lassen laufen, bis der Parameter $0$ erreicht hat ( wir lassen die While-Schleife laufen, bis die Bedingung erfüllt wurde) oder ( wir lassen die TM rechnen bis sie anhält (oder nicht))

Das heißt also, um eine rekursive Funktion als For-Loop darzustellen, brauchen wir wieder eine konzeptuelle Idee, die am Ende eine While-Schleife wäre bzw in der Konstruktion dieser entspricht!

Lambda-Kalkül ist Turing-äquivalent

Wir wollen uns jetzt anschauen, warum niemand zeigt, dass das $\lambda$-Kalkül turing-äquivalent ist (weil es schwierig ist).

Definition Lambda-Kalkül

[!Definition]

Sei $V$ eine abzählbare Menge an Variablen - eine Teilmenge daraus kann im Vorhinein als Konstanten definiert werden.

Wir definieren die $\lambda$-Terme - oder einfach Terme - folglich induktiv:

welche drei Schritte brauchen wir? #card

1. Jede Variable $x\in V$ ist ein Term
2. Sind $M,N$ Terme, dann ist auch die Applikation $MN$ einen Term
3. Wenn $M$ ein Term ist und $x\in V$ eine Variable, dann ist die Abstraktion $(\lambda x,M)$ auch ein Term.

Es gibt hierfür noch Konventionen: Konvention Linksassoziation:

Die Notation $M_1,M_2,M_3\dots ,M_n$ steht für die folgen Applikation $((\dots ,(((M_1{M}_2)M_3)\dots )M_n))$

$\lambda x,M$ bedeutet, dass der Wert $x$ durch den Term in M gebunden wird ( in einem Programm, dann einfach die Anwendung einer Variable, die wir als Parameter in einer Funktion abgeben)

Konversion

Die Rechenregeln des $\lambda$-Kalküls sind Überführungen von einem Term in einen anderen, die die gleiche Semantik haben.

Dafür können wir zwei Konversionen betrachten.

[!Definition] $\lambda$ Konversionen

Es gibt zwei Konversionen, die wir betrachten: $\alpha ,\beta$

was besagen beide? #card

• Die $\alpha$-Konversion (die einfachere) beschreibt folgende Umformung / Vereinfachung: $$\lambda V.M\to \lambda W.M[W\leftarrow V];W\notin FV(M)$$ Einfacher also: “Freie Variablen können beliebig umbenannt werden”

• Die $\beta$-Konversion (welche so das wichtigste des Theorems ist!) beschreibt die Applikation von Termen: $$(\lambda x.M)M\to M[x<-N]$$

  • Also keine freie Variable in $N$ darf durch die Substitution in $M$ gebunden werden

• Die $\beta$-Konversion ist die “Anwendung einer (anonymen!) Funktion”, $M$ ist dabei der Funktionskörper, $x$ ihr Argument und $N$ der Wert des Argumentes!

Ein Term $M$ ist ferner dann in der $\beta$-Normalform, wenn es keine $\beta$-Konversion mehr gibt, die auf $M$ angewendet werden können!

Wir nennen noch $M$ einen Kombinator, wenn er keine freien Variablen enthält ( also er nimmt meist Werte und kann sie entsprechend wieder darstellen - ohne viel zu bearbeiten/)

[!Tip]

Es ist nicht entscheidbar, ob ein gegebener Term in $\beta$-Normalform ist. Es ist auch nicht entscheidbar, ob ein gegebener Termin eine $\beta -$Normalform hat oder nicht

(Siehe church, 1965, Theorem XIV, XV)

Wir wollen dabei noch einige grundlegende beispiele für Terme betrachten, die wir später benötigen werden:

Grundlegende Beispiele | $\lambda$-Kalkül

[!Bsp] Identität $I$

Können wir folgend darstellen: $I=\lambda x.x$ ist ein Kombinator mit der Eigenschaft $IM\to M$, also bei einer Eingabe eines Termes $M$ wird sie am Ende nur den Termin zurückgeben@

[!Defiition] Konstanten-Kombinator

Wir bezeichnen jetzt den Kombinator $K=\lambda x.\lambda y.x$ als den Kombinator, der eine Konstante ausgeben kann.

Also unter jeder Eingabe werden wir einfach eine bestimmte Konstante zurückgeben!

Also $KMN\to M$ für alle Terme $M$

Wir wollen noch Booleans einbringen:

[!Req] Booleans mit $\lambda$-Kalkül

Man kann den Kombinator auch verwendet, um logische Werte $T$ oder $F$ darzustellen:

• $T=K$ ist dann True
• $F$ für False repräsentieren wir mit $\lambda x.I=F$

Denn $Tab=a$ und ferner $Fab=b$

Man kann mit dem $\lambda$p