Berechenbare Funktion |
bit
Grünschnabel
Dabei seit: 13.10.2007
Beiträge: 2
|
|
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!!
|
|
13.10.2007 23:21 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
"Sie müssen bei dieser Aufgabe keine Korrektheitsbeweise führen." sagt aus, dass du keinen Korrektheitsbeweis führen musst.
|
|
14.10.2007 13:14 |
|
|
bit
Grünschnabel
Dabei seit: 13.10.2007
Beiträge: 2
|
|
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.
|
|
14.10.2007 22:56 |
|
|
|