Papier falten

Gleichungssysteme für unendliche Folgen

In eine Programmiersprache mit Bedarfsauswertung können unendliche Objekte definiert und endliche Teilstücke davon berechnet werden. Wir betrachten insbesondere unendliche Folgen (Listen, Streams).

Die Gleichung

let zz = 1 : (-1) : zz

definiert die Zick-Zack-Folge. Wir berechnen ein Anfangsstück:

take 10 zz
  ==> [1,-1,1,-1,1,-1,1,-1,1,-1]

Die Abwechsel-Funktion

let abw (x:xs) ys = x : abw ys xs

verschränkt zwei Folgen. Wir definieren damit

let pf = abw zz pf

Wir berechnen die ersten Elemente dieser Folge, indem wir wiederholt die Gleichungen aus den Definitionen von zz, abw und pf als Ersetzungsregeln anwenden (ein Vorkommen der linken Seite wird durch die rechte Seite ersetzt).

pf = abw zz pf
   = abw (1 : -1 : zz) pf
   = 1 : abw pf (-1 : zz)
   = 1 : abw (1 : abw pf (-1 : zz)) (-1 : zz)
   = 1 : 1 : abw (-1 : zz) (abw pf (-1 : zz))
   = 1 : 1 : -1 : abw (abw pf (-1 : zz)) zz

Papier falten

Dieses pf heißt Papier-Falt-Folge. Wir nehmen einen Papierstreifen, halten ein Ende A fest und falten das andere B nach oben, bis es auf A liegt, und streichen den Streifen glatt. Dadurch entsteht ein Knick in der Mitte M des Streifens. Wir halten A und B fest und falten M nach oben, bis es auf A (und B) liegt. Wir wiederholen diesen Vorgang und falten den Streifen dann auseinander.

Wir stellen fest: die Folge der Knicke (von A aus gesehen) ist genau der Anfang von pf

take 7 pf
  ==> [1,1,-1,1,1,-1,-1]

wenn wir 1 als “Knick nach oben” und -1 als “Knick nach unten” auffassen.

Zur Begründung betrachten wir die Teilfolge auf der ersten, dritten, usw., Position

[1, *, -1, *, 1, *, -1]

Sie gehört zu den Knicken, die die letzte Faltung erzeugt hat, und ist tatsächlich genau die Zickzackfolge.

Die Teilfolge auf der zweiten, vierten, usw., Position

[*, 1, *, 1, * ,-1, *]

ist die Folge, die aus den Faltungen davor entstanden ist, also ein Anfangsstück der Papierfaltfolge selbst.

Damit haben wir gezeigt, daß die Papierfaltfolge die Gleichung

pf == abw zz pf

erfüllt.

Eine geometrische Eigenschaft

Wir falten den Streifen wieder zusammen, aber nicht vollständig, sondern so, daß in jedem Knick ein rechter Winkel liegt.

Da Bild zeigt das Resultat für 15 Knicke, also nach 4 Faltugen. Dabei ist jeder Winkel etwas kleiner als ein rechter, damit man der Kurve besser folgen kann. Der Beginn der Folge ist rechts (nicht links).

falt-a

Nach 9 Faltungen, also 511 Knicken, sieht der Streifen so aus:

falt-b

Wir erhalten eine Kurve, die sich an vielen Stellen berührt, aber nie schneidet. Das ist besser zu sehen, wenn wir den Winkel wieder etwas verringern:

falt-c

Binärzahlen und Papier (Zusatz)

Man den Eintrag in der Papierfaltfolge an der Stelle i aus der Binärdarstellung von i bestimmen. Dazu ist es zweckmäßig, die Zählung der Indizes bei 1 zu beginnen.

Die Folge der Binärdarstellungen der Indizes ist

let bz = [ 1 ] : ( bz >>= \ z -> [ 0 : z, 1 : z ] )

Hier verwenden wir die Operation >>=, die auf jedes Element der Liste (linkes Argument) eine Funktion (rechtes Argument) anwendet, die eine Liste erzeugt, und alle diese Teillisten verkettet.

take 5 bz
  ==> [[1],[0,1],[1,1],[0,0,1],[1,0,1]]
take 5 bz >>= \ z -> [ 0 : z, 1 : z ] 
  ==> [[0,1],[1,1],[0,0,1],[1,0,1],[0,1,1],[1,1,1],[0,0,0,1],[1,0,0,1],[0,1,0,1],[1,1,0,1]]

Binärzahlen erscheinen hier mit dem niederwertigsten Bit links, z.B. [0,1,0,1] bedeutet 10. Das können wir nachrechnen:

let bin z = foldr (\x y-> x + 2*y) 0 z
bin  [0,1,0,1]
  ==> 10

Damit prüfen wir, daß wir tatsächlich die richtigen Binärzahlen haben:

take 10 $ map bin bz
  ==> [1,2,3,4,5,6,7,8,9,10]

Auf den ungeraden Positionen 1, 3, 5, .. von pf finden wir, nach Definition, die Zickzackfolge zz.

Die ungeraden Zahlen sind genau die mit einer 1 in der ersten (linken) Binärstelle.

Auf den geraden Positionen 2, 4, 6, .. von pf finden wir pf selbst, und auf den ungeraden Positionen dieser Teilfolge, also auf Positionen 2, 6, 10, .. der Originalfolge, wieder zz.

Die Binärdarstellungen dieser Positionen beginnen mit [0,1].

Weiter verlangsamte Zickzackfolgen finden wir auf Positionen, deren Binärdarstellungen mit [0,0,1] beginnen, usw.

Die Elemente einer solchen Folge hängen von der nächsten Binärziffer des Index ab.

Um den Eintrag von pf an der Stelle i zu bestimmen, überspringen wir also in der Binärdarstellung von i alle führenden (niederwertigen) Nullen (dropWhile (==0)) sowie die die folgende Stelle (tail), auf der eine 1 steht, und betrachten die nächste Stelle: steht dort 0 (oder gar nichts), falten wir nach oben (1), sonst nach unten (-1).

import Data.List (isPrefixOf)
let get z = if isPrefixOf [1] $ tail $ dropWhile (==0) z then -1 else 1

Wir wenden diese Funktion elementweise auf den Anfang der Binärzahlenfolge an und erhalten tatsächlich genau die Papierfaltfolge:

take 10 $ map get bz
  ==> [1,1,-1,1,1,-1,-1,1,1,1]
take 10 $ pf
  ==> [1,1,-1,1,1,-1,-1,1,1,1]

Eine unendliche Folge, deren Elemente man aus der Darstellung des Index in einer fixierten Basis (hier 2) durch eine einfache Rechnung bestimmen kann, heißt automatisch. Genauer: für jede Ziffer z (hier: -1 und 1) ist die Menge der (Binär)darstellungen der Indizes i, auf denen z vorkommt, eine reguläre Sprache (hier: die Index-Sprache für z =  − 1 ist 0*11(0 + 1)*).

Die Fibonacci-Folge

Wir benutzen die Operation >>=, die auf jedes Element der Liste (linkes Argument) eine Funktion (rechtes Argument) anwendet, die eine Liste erzeugt, und alle diese Teillisten verkettet. Beispiel:

[0,1,0] >>= \ case 0 -> [0,1] ; 1 -> [0]
  ==>  [0,1] ++ [0] ++ [0,1]  ==>  [0,1,0,0,1]

Wir suchen eine Zahlenfolge mit der Eigenschaft

f  =  f >>= \ case 0 -> [0,1] ; 1 -> [0]

Diese Gleichung ist jedoch nicht geeignet, um die Folge auszurechnen: um das erste Element von f zu bestimmen, benötigen wir bereits das erste Element von f.

Mit einem Trick geht es doch. Wir wissen, daß die Folge mit 0 beginnt. Also gilt

f = 0 : tail f

Wir setzten die vorige Gleichung ein und erhalten

f = 0 : tail ( f >>= \ case 0 -> [0,1] ; 1 -> [0] )

Diese Definition ist produktiv, d.h., wir können sie als Ersetzungsregel (von links nach rechts) benutzen, um jedes Folgenelement zu bestimmen. Um weniger zu schreiben, verwenden wir

let phi = \ case 0 -> [0,1] ; 1 -> [0]

Dann gilt

f = 0 : tail ( f >>= phi)
  = 0 : tail ( (0 : tail ( f >>= phi)) >>= phi )
  = 0 : tail ( [0] >>= phi ++ tail (f >>= phi) >>= phi)
  = 0 : tail ( [0,1] ++ tail (f >>= phi) >>= phi )
  = 0 : 1 : tail (f >>= phi) >>= phi

Wir erhalten

take 10 f
  ==> [0,1,0,0,1,0,1,0,0,1]

Zur Probe berechnen wir

take 10 f >>= phi
  ==> [0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0]

Diese Folge heißt (unter anderem) deswegen Fibonacci-Folge, weil sie auch der Limes dieser Konstruktion ist: w0 = [0], w1 = [0, 1], wk + 2 = wk + 1wk, und die Längen der dabei vorkommenden Teilwörter Fibonacci-Zahlen 1, 2, 3, 5, 8, .. sind, wie man leicht zeigen kann.

Wir bemerken als ein Kuriosum, daß f beliebig lange Palindrome enthält, beschäftigen uns jetzt jedoch mit einer geometrischen Eigenschaft.

Die Treppenkurve der Fibonacci-Folge

Wir erhalten aus der Fibonacci-Folge einen Streckenzug, wenn wir jede 0 durch einen Schritt nach rechts und jede 1 durch einen Schritt nach oben ersetzen.

Im Unterschied zum Papierfalten verwenden wir keine relativen Winkel (relativ zum vorigen Streckenabschnitt), sondern absolute (zum festen Koordinatensystem).

fib-a

Wir beobachten, daß der Streckenzug einen gleichmäßigen Anstieg annhähert, und werden das präzisieren und beweisen.

Das Fibonacci-Wort ist mechanisch: der Streckenzug verläuft in einem durch zwei Parallelen begrenzten Korridor.

fib-b

Die untere Linie geht durch (0,  − 1), die obere durch (0, q), der gemeinsame Anstieg ist q, mit $q = (\sqrt{5}-1)/2$.

Durch diesen Korridor und den Startpunkt (0, 0) wird der Streckenzug eindeutig bestimmt: für jeden Punkt (x, y) im Korridor liegt entweder (x + 1, y) oder (x, y + 1) im Korridor (Schritt nach rechts oder Schritt nach oben).

Wir beweisen, daß das tatsächlich die oben definierte Folge f beschreibt.

Wir ersetzen in der Folge f jede 0 (Strecke nach rechts) durch eine Strecke nach oben, gefolgt von einer Schräge nach unten rechts, so daß wir am gleichen Ziel ankommen. Wir erhalten den roten Streckenzug. Er liegt im Korridor mit um 1 nach oben verschobener oberer Grenze.

fib-c

Wir spiegeln dieses Bild an der Geraden x = y

fib-d

Durch eine Scherung, bei der die x-Achse erhalten bleibt, die Gerade y = 1 um 1 nach rechts verschoben, usw., wird der breite Korridor auf den ursprünglichen abgebildet und die Winkel des roten Streckezuges sind nun rechte. Weil rechwinklige Einheitsstreckenzüge in diesem Korridor eindeutig sind, ist das Bild des roten Streckenzuges gleich der originalen Treppenlinie.

fib-e

Daraus folgt, daß die Treppenlinie invariant unter der gleichzeitigen Ersetzung von 0 durch 01 und 1 durch 0 ist, d.h., sie stimmt wirklich mit der oben definierten Folge f überein.

Programmierung

Die Diagramme habe ich mit diagrams gezeichnet, hier ist der Quelltext.

Literatur