40
Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2 falls a k gerade a k+1 = 3a k +1 falls a k ungerade

Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Embed Size (px)

Citation preview

Page 1: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Die Collatz-Folge

a0 selbst wählen ( N)

ak+1 = ak/2 falls ak gerade

ak+1 = 3ak+1 falls ak ungerade

Page 2: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Beispiele

15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

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

Page 3: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Collatz-Zahlen

• Def.: Eine Zahl n N heißt Collatz-Zahl, wenn die Collatz-Folge mit a0 = n bei 1 endet (4–2–1)

• Wir kennen derzeit für die Menge der Collatz-Zahlen keine Turingmaschine, die bei Eingabe einer Zahl sicher anhält und die Ausgabe ja oder nein liefert.

• Es ist nicht bekannt, ob die Menge entscheidbar ist.• Sollten alle natürlichen Zahlen Collatz-Zahlen sein, so ist

die Menge entscheidbar.• Leicht ist es hingegen, eine Turingmaschine zu

entwickeln, die mit ja anhält, falls es sich bei der Eingabe um eine Collatz-Zahl handelt, und andernfalls nicht anhält.

Page 4: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Das Halteproblem

Kann man eine Turingmaschine bauen, die von einer anderen Turingmaschine feststellt, ob diese hält oder nicht?

Page 5: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Hält

Stellt fest, ob TM t hält oder nicht

? j / n

Hält

TM t hält vielleicht manchmal und manchmal nicht, je nach Eingabe

Page 6: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Hält

Stellt fest, ob TM t auf Eingabe w hält oder nicht

? j / n

Hält

Was sollte auf dem Band stehen?

Page 7: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Hält

Stellt fest, ob TM t auf Eingabe w hält oder nicht

t # w j / n

Hält

Wenn TM t bei Eingabe w hält, stoppt Hält mit j, andernfalls mit n

Page 8: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Frage:

Kann man so eine Turingmaschine

Hält

basteln?

Page 9: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Annahme 1:

Es gibt so eine Turingmaschine

Hält

Page 10: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Fragen:

• Angenommen, wir können die Turingmaschine Hält programmieren.

• Welche Auswirkung hätte das auf die Goldbachsche Vermutung?

• Welche Auswirkung hätte das auf das Collatz-Problem?• Welche Auswirkung hätte das auf die Software-

Industrie?• Hausaufgabe!

Page 11: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

1. TM: Hält

Stellt fest, ob TM t auf Eingabe w hält

t # w j / n

Hält

Wenn TM t bei Eingabe w hält, stoppt Hält mit j, andernfalls mit n

Page 12: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

2. TM: Kopierer

Kopiert den Bandinhalt

h a l l o # h a l l o

KopiererVerdoppeln

Page 13: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

3. TM: Seltsam

?

t j /

Seltsam

Eingabe TM t, Ausgabe stopp mit j oder Endlosschleife

Page 14: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Seltsam ruft zuerst TM Kopierer auf, danach TM Hält

t j /

Seltsam

Kopierer

Hält

1.

2.

Page 15: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Seltsam ruft nun noch TM Hält auf

t # t

Seltsam

Hält2.

Page 16: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Was hat Hält auf das Band geschrieben?

j: Dann geht Seltsam in eine Endlosschleife.

n: Dann ersetzt

Seltsam das n durch ein j und stoppt.

t # t j / n

Seltsam

Page 17: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

j: Dann geht Seltsam in eine Endlosschleife.

t # t

Seltsam

Page 18: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

n: Dann ersetzt

Seltsam das n durch ein j und stoppt.

t # t j

Seltsam

Page 19: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

spezielle Eingabe Seltsam

Seltsam

SeltsamSeltsam bekommt sich

selbst als Eingabe!

Page 20: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Frage:

Hält Seltsam bei Eingabe Seltsam?

Akzeptiert Seltsam sich selbst?

Page 21: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Annahme 2 a):

Seltsam hält bei Eingabe Seltsam

Page 22: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Widerspruch!

Annahme 2 a)

Seltsam hält bei Eingabe Seltsam

ist unmöglich!

Page 23: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Annahme 2 b):

Seltsam hält bei Eingabe Seltsam nicht

Page 24: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Widerspruch!

Annahme 2 b)

Seltsam hält bei Eingabe Seltsam nicht

ist unmöglich!

Page 25: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Annahme 1:

Es gibt so eine Turingmaschine

Hält

Schlussfolgerung:

Diese Annahme ist unmöglich!

Page 26: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Frage:

Hält Seltsam bei Eingabe Seltsam?

Akzeptiert Seltsam sich selbst?

Page 27: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Annahme 2 a):

Seltsam hält bei Eingabe Seltsam

Page 28: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Annahme 2 a): Seltsam hält bei Eingabe Seltsam

Seltsam

Seltsam

Kopierer

Hält

1.

2.

Page 29: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Annahme 2 a): Seltsam hält bei Eingabe Seltsam

Seltsam # Seltsam

Seltsam

Hält2.

Page 30: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Was hat Hält auf das Band geschrieben?

j: Dann geht Seltsam in eine Endlosschleife.

n: Dann ersetzt

Seltsam das n durch ein j und stoppt.

Seltsam # Seltsam j

Seltsam

Annahme 2 a): Seltsam hält bei Eingabe Seltsam

Page 31: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

j: Dann geht Seltsam in eine Endlosschleife.

Seltsam Seltsam

Seltsam

Annahme 2 a): Seltsam hält bei Eingabe Seltsam

Page 32: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Widerspruch!

Annahme 2 a)

Seltsam hält bei Eingabe Seltsam

ist unmöglich!

Page 33: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Annahme 2 b):

Seltsam hält bei Eingabe Seltsam nicht

Page 34: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Annahme 2 b): Seltsam hält bei Eingabe Seltsam nicht

Seltsam

Seltsam

Kopierer

Hält

1.

2.

Page 35: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Annahme 2 b): Seltsam hält bei Eingabe Seltsam nicht

Seltsam # Seltsam

Seltsam

Hält2.

Page 36: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

Was hat Hält auf das Band geschrieben?

j: Dann geht Seltsam in eine Endlosschleife.

n: Dann ersetzt

Seltsam das n durch ein j und stoppt.

Seltsam # Seltsam n

Seltsam

Annahme 2 b): Seltsam hält bei Eingabe Seltsam nicht

Page 37: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

TM Seltsam

n: Dann ersetzt

Seltsam das n durch ein j und stoppt.

Seltsam Seltsam j

Seltsam

Annahme 2 b): Seltsam hält bei Eingabe Seltsam nicht

Page 38: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Widerspruch!

Annahme 2 b)

Seltsam hält bei Eingabe Seltsam nicht

ist unmöglich!

Page 39: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Annahme 1:

Es gibt so eine Turingmaschine

Hält

Schlussfolgerung:

Diese Annahme ist unmöglich!

Page 40: Die Collatz-Folge a 0 selbst wählen ( N) a k+1 = a k /2falls a k gerade a k+1 = 3a k +1falls a k ungerade

Halteproblem

Resümee: Es gibt keine Turingmaschine, die bei Eingabe einer Turingmaschine t und eines Wortes w entscheidet, ob t bei Eingabe von w hält oder nicht.

Die Menge aller Paare (t,w) [t, w, wie oben] derart, dass t auf w hält, ist

nicht entscheidbar.

Satz von Turing (1936)