Day: 5 May 2010

Man braucht mindestens 2N-1 Bewegungen, um das Problem zu lösen. Bei 64 Scheiben braucht man also 264-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.… Continue reading Turingmaschinen