3.4 \(\mu\)-Rekursion

Primitive Rekursion erlaubt uns Schleifen, allerdings nur in einer sehr restriktiven Form:
  1. Wir müssen anfangs bereits angeben, wie oft wir die Schleife durchlaufen wollen;
  2. wir dürfen nur eine lokale Variable mitführen (und den Iterationsindex).
Der zweite Punkt ist keine echte Beschränkung, wie wir gesehen haben: wenn wir zwei lokale Variablen \(a,b\) führen wollen, können wir die via der Bijektion \({\rm pair} : \N^2 \rightarrow \N\) in eine natürliche Zahl codieren. Der erste Punkt allerdings scheint eine echte Beschränkung zu sein: wir wissen schließlich nicht immer, wie oft wir eine Tätigkeit wiederholen müssen, bis wir fertig sind, und ob wir überhaupt jemals fertig werden. Sie kennen vielleicht die Collatz-Vermutung.

Die Collatz-Vermutung

Wir definieren eine Funktion $f: \N_+ \rightarrow \N_+$ wie folgt:

\begin{align*} f : \N_+ & \rightarrow \N_+ \\ n & \mapsto \begin{cases} n/2 & \textnormal{ if $n$ even} \\ 3n+1 & \textnormal{ if $n$ odd.} \end{cases} \end{align*}

Für eine natürliche Zahl $n$ können wir dann die Collatz-Folge definieren: $n, f(n), f(f(n)), ...$. Man sieht leicht, dass diese Folge in einer Schleife landen kann:

\begin{align*} 13 \mapsto 40 \mapsto 20 \mapsto 10 \mapsto 5 \mapsto 16 \mapsto 8 \mapsto 4 \mapsto 2 \mapsto 1 \mapsto 4 \mapsto 2 \mapsto 1 \dots \end{align*}

Wir beenden die Sequenz daher üblicherweise, wenn wir bei 1 (und somit in dieser Dreierschleife) gelandet sind. Es kann allerdings etwas länger dauern:

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Oder noch länger. Wenn wir mit 27 beginnen, dann erhalten wir die Folge
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Experimentieren Sie! Ich habe dafür die Html-Seite collatz.html erstellt. Es scheint: egal, wo Sie anfangen, Sie enden immer bei 1. Allerdings wissen wir nicht im Voraus, wie oft wir die Funktion $f$ anwenden müssen. Und wir wissen nicht einmal, ob man immer bei 1 ankommt, ob es andere Zyklen gibt oder ob es Startwerte gibt, für die die Folge einfach nach Unendlich divergiert. Bis zum heutigen Tage (Stand 30. April 2024) hat sich die Collatz-Vermutung zahlreichen Lösungsversuchung widersetzt und demonstriert eindrucksvoll, dass auch mathematische Probleme mit sehr einfacher Formulierung extrem schwierig sein können.

While-Schleifen

Eine Einschränkung primitiv-rekursiver Funktionen ist also, dass wir immer vor der Schleife angeben müssen, wie oft diese durchlaufen werden soll. Es gibt also keine while-Schleifen. Führen wir diese nun ein. 

def While (condition, step):
	def f(x):
		temp = x
		while (condition(temp)):
			temp = step(temp)
		return temp 
	return f

Übungsaufgabe Schreiben Sie mit Hilfe von While, PrimRec und Comp eine Funktion collatzList, die aus einer Zahl die Collatz-Folge baut, also 

collatzList(7)                            
[]