Informatiker Board | Druckvorschau: Berechenbare Funktion

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Berechenbare Funktion (http://www.informatikerboard.de/board/thread.php?threadid=277)

Geschrieben von bit am 13.10.2007 um 23:21:

Berechenbare Funktion

Hallo Wink

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? verwirrt

Danke!!

Geschrieben von Tobias am 14.10.2007 um 13:14:

"Sie müssen bei dieser Aufgabe keine Korrektheitsbeweise führen." sagt aus, dass du keinen Korrektheitsbeweis führen musst. großes Grinsen

Geschrieben von bit am 14.10.2007 um 22:56:

Ja, das hab' ich mir ja auch gedacht.
Aaaaber verwirrt

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.