Es gibt Probleme, die von klugen Menschen gelöst, aber nicht von einem Computer ausgerechnet werden können, obwohl sie vergleichsweise einfach zu erklären sind. Dabei ist die Programmierung einfach, aber die Laufzeit bis zu einem Ergebnis kommt der Ewigkeit schon bedenklich nahe. Hier ist so ein Beispiel. Es wird eine Konstruktion für eine Zahlenfolge angegeben, die verständlich und trotzdem geheimnisvoll ist. Eine der Fragen, die man sich stellt, ist: kommen nur die Zahlen 1, 2, 3 und 4 vor, oder auch noch 5 oder andere Zahlen? Mathematiker haben bewiesen, dass die Zahl 5 vorkommt, geschätzt etwa an der Position 10~094~(10~094~23). Soweit kann kein Computer rechnen. Zum Vergleich das Universum hat etwa 10~094~80 Wasserstoffatome (das ist unpräzise formuliert, aber die Größenordnung ist der relevante Teil). Als Bonus gibt es zum Abschluss noch ein ungelöstes Problem - falls jemand selber knobeln möchte.
A Slow-Growing Sequence Defined by an Unusual Recurrence The first occurrence of a number in Gijswijt's sequence A090822