Moin,
eine Frage zum Halteproblem bei S&A... im Skript wird der Beweis geführt, dass der Busy Beaver schneller wächst als jede andere Funktion, somit wird der Busy Beaver als nicht turing-berechenbar angegeben.
Wie aber ist der Zusammenhang zwischen dem Busy Beaver und dem Halteproblem? Wenn ich z.B. anhand des Busy Beaver zeigen soll, dass das Halte-Problem nicht turing-berechenbar ist, wie gehe ich da vor? Ist es so einfach, wie ich es mir vorstelle? Dass nämlich ein Turingprogramm, das den Busy Beaver berechnen sollte, niemals feststellen kann, ob ein Turingprogramm mit n Zuständen jemals hält? Und ist der Grund dafür, dass dieses Busy-Beaver-Turingprogramm einfach nicht genügend Zustände besitzen kann, um den Busy Beaver zu berechnen? Oder dass der Busy Beaver so ungemein schnell wächst?
Worüber ich froh wäre, ist eine möglichst exakte Darstellung der Zusammenhänge, damit man sich in der Klausur nicht alles erneut zusammenreimen muss. Aber irgendwie stoße ich auf zu viele Unklarheiten...
Vielen Dank schon mal für Tipps,
Br3ndel
S&A: Halteproblem + Busy Beaver
Moderator: (M) Mod.-Team Allgemein
Einfach ein Widerspruchsbeweis: Ang., das Halteproblem wäre lösbar. Dann könnte man für jedes Turingprogramm mit n Zuständen sagen, ob es in endlich vielen Schriten terminiert. Dann wäre Busy-Beaver berechnbar. Und das ist ein Widerspruch.
Five exclamation marks, the sure sign of an insane mind. Terry Pratchett
Oh man und ich dachte, hier gehts um was interessantes
garnichts ?!xAnO hat geschrieben:obwohl der thread schon ein bisschen alt ist:
ist der BB eigentlich NP? das kam nun in ein paar klausuren vor und ich konnte konkret nichts darüber finden.
wenn ein Entscheidungsproblem P € NP ist:
"Für eine gegebene Lösung kann in polynomialZeit entschieden werden, ob sie das Probelm mit 'ja' löst."
Und du fragst ob des BB € NP ist ?
vllt sollte ich noch anhängen: du weisst das BB nicht turing-berchenbar ist ?
