Berechenbare Funktion |
13.10.2007, 23:21 | Auf diesen Beitrag antworten » |
bit | Berechenbare Funktion Hallo Ich bin neu hier und habe gleich mal eine Frage. Ich habe hier eine Aufgabe (a,b), die eingeleitet wird mit "Sie müssen bei dieser Aufgabe keine Korrektheitsbeweise führen." In b) soll man nun durch graphische Angabe eines Flussdiagramms einer verallgemeinerten Registermaschine zeigen, dass die Funktion f(x,y)... berechenbar ist. Und dann begründen, warum f berechenbar ist. Ich habe jetzt das Flussdiagramm gezeichnet und begründet, warum f berechenbar ist (weil alle Tests und Funktionen rekursiv (mit Begründung warum) sind). Reicht das schon oder muss ich nun noch mittels vollständiger Induktion beweisen? Danke!! |
|
|
14.10.2007, 13:14 | Auf diesen Beitrag antworten » |
Tobias | "Sie müssen bei dieser Aufgabe keine Korrektheitsbeweise führen." sagt aus, dass du keinen Korrektheitsbeweis führen musst. |
14.10.2007, 22:56 | Auf diesen Beitrag antworten » |
bit | Ja, das hab' ich mir ja auch gedacht. Aaaaber Ich frage mich wie man ohne vollständige Induktion "begründen" soll, dass f berechenbar ist. Einfach nur zu sagen, dass f berechenbar ist wenn es eine Registermaschine M gibt mit f = fM. Und dass alle Tests und Funktionen der Registermaschine rekursiv und somit fM berechenbar ist. Reicht das dann wirklich schon aus um das zu "begründen"? Danke. |
|