Die Collatz-Folge
a0 selbst wählen ( N)
ak+1 = ak/2 falls ak gerade
ak+1 = 3ak+1 falls ak 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
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.
Das Halteproblem
Kann man eine Turingmaschine bauen, die von einer anderen Turingmaschine feststellt, ob diese hält oder nicht?
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
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?
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
Frage:
Kann man so eine Turingmaschine
Hält
basteln?
Annahme 1:
Es gibt so eine Turingmaschine
Hält
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!
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
2. TM: Kopierer
Kopiert den Bandinhalt
h a l l o # h a l l o
KopiererVerdoppeln
3. TM: Seltsam
?
t j /
Seltsam
Eingabe TM t, Ausgabe stopp mit j oder Endlosschleife
TM Seltsam
Seltsam ruft zuerst TM Kopierer auf, danach TM Hält
t j /
Seltsam
Kopierer
Hält
1.
2.
TM Seltsam
Seltsam ruft nun noch TM Hält auf
t # t
Seltsam
Hält2.
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
TM Seltsam
j: Dann geht Seltsam in eine Endlosschleife.
t # t
Seltsam
TM Seltsam
n: Dann ersetzt
Seltsam das n durch ein j und stoppt.
t # t j
Seltsam
TM Seltsam
spezielle Eingabe Seltsam
Seltsam
SeltsamSeltsam bekommt sich
selbst als Eingabe!
Frage:
Hält Seltsam bei Eingabe Seltsam?
Akzeptiert Seltsam sich selbst?
Annahme 2 a):
Seltsam hält bei Eingabe Seltsam
Widerspruch!
Annahme 2 a)
Seltsam hält bei Eingabe Seltsam
ist unmöglich!
Annahme 2 b):
Seltsam hält bei Eingabe Seltsam nicht
Widerspruch!
Annahme 2 b)
Seltsam hält bei Eingabe Seltsam nicht
ist unmöglich!
Annahme 1:
Es gibt so eine Turingmaschine
Hält
Schlussfolgerung:
Diese Annahme ist unmöglich!
Frage:
Hält Seltsam bei Eingabe Seltsam?
Akzeptiert Seltsam sich selbst?
Annahme 2 a):
Seltsam hält bei Eingabe Seltsam
TM Seltsam
Annahme 2 a): Seltsam hält bei Eingabe Seltsam
Seltsam
Seltsam
Kopierer
Hält
1.
2.
TM Seltsam
Annahme 2 a): Seltsam hält bei Eingabe Seltsam
Seltsam # Seltsam
Seltsam
Hält2.
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
TM Seltsam
j: Dann geht Seltsam in eine Endlosschleife.
Seltsam Seltsam
Seltsam
Annahme 2 a): Seltsam hält bei Eingabe Seltsam
Widerspruch!
Annahme 2 a)
Seltsam hält bei Eingabe Seltsam
ist unmöglich!
Annahme 2 b):
Seltsam hält bei Eingabe Seltsam nicht
TM Seltsam
Annahme 2 b): Seltsam hält bei Eingabe Seltsam nicht
Seltsam
Seltsam
Kopierer
Hält
1.
2.
TM Seltsam
Annahme 2 b): Seltsam hält bei Eingabe Seltsam nicht
Seltsam # Seltsam
Seltsam
Hält2.
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
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
Widerspruch!
Annahme 2 b)
Seltsam hält bei Eingabe Seltsam nicht
ist unmöglich!
Annahme 1:
Es gibt so eine Turingmaschine
Hält
Schlussfolgerung:
Diese Annahme ist unmöglich!
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)