Die Webseiten der Fachschaft Informatik am ERG Saalfeld

einseitig entscheidbar

Wie schon auf der Seite zur Entscheidbarkeit angegeben, gibt es Ja-Nein-Fragen, die nur eine Antwort ermöglichen, also nur 'ja' oder nur 'nein'. Diese Fragen nennen wir einseitig entscheidbar.

wundersame Zahlen oder das 3n+1 - Problem

Wundersame Zahlen nennt Hofstadter[2] solche Zahlen, die Startwerte der Collatzfolge[1] sind. Andernfalls nennt er diese Zahlen "unwundersam".

Wir nehmen uns eine natürliche Zahl n z.B. n = 28.
Wir betrachten jetzt die Folge, die nach folgendem Bildungsgesetz entsteht:

ist die Zahl ungerade, dann bilde 3n+1
ist die Zahl gerade, dann halbiere diese, also n/2
wiederhole das, solange bis du eine 1 erhältst.

für n = 28 ergibt sich:

28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Zusammengefasst: Die Frage, ob eine Zahl wundersam ist oder nicht, lässt sich nur dann beantworten, wenn die Zahl wundersam ist. Andernfalls kann keine Entscheidung getroffen werden! Oder anders formuliert, ob eine Zahl unwundersam ist, kann nicht entschieden werden.

Aufgabe

schreiben Sie ein Programm, welches von einer Zahl n die Collatzfolge ausgibt, indem dieses Bildungsgesetz umgesetzt wird.
Die Zahl n soll als Parameter an das Programm übergeben werden.
Testen Sie Ihr Programm für 7, 19, 28, 8 ... (siehe Screenshot)
Ist das umgesetzte Bildungsgesetz ein Algorithmus?

Weblinks

zurück