Man braucht mindestens 2^N-1 Bewegungen, um das Problem zu lösen.

Bei 64 Scheiben braucht man also 2⁶⁴-1 Bewegungen. Bei 10 Sekunden pro Bewegung bräuchte man 5,8 Billionen Jahre.

Uff!

Merke

Mit keinem heutigen Rechner und keiner heutigen Programmiersprachen können Funktionen berechnet werden, die nicht auch mit einer Turingmaschine berechnet werden können.

Die Turingmaschine ist ein allgemeines Modell für die Berechenbarkeit.

Entscheidbarkeit

Ein Problem P ist entscheidbar, wenn es einen Algorithmus gibt, der für P mit Ja oder Nein beantwortet werden kann.

Unentdcheidbare Probleme

Z.B. Kommt eine bestimmte Ziffernfolge im Nachkommsteil von Pi vor?