Frage zur Berechenbarkeit, wenn h im "if" steht

[CloneCommander]

Hi!

ich bin mir gerade unsicher, wenn ich z.b. die Funktionen g und h habe, g berechenbar und h nicht, ist dann folgendes Bsp. berechenbar?

(das soll eine Fallunterscheidung sein)
f(x) =
-> 0, falls h(x) = 0
-> g(x) sonst

g(x) und 0 ist berechenbar, klar - aber darf ich denn eine nicht berechenbare funktion im "falls" haben? Also tritt wenn h(x) nicht geht der Fall einfach nie ein oder wird dadurch ganz f(x) nicht berechenbar?
oder reicht es, dass g(x) und 0, also die Rückgabewerte, berechenbar sind?

MfG CC

[Simon Siegler]

In diesem Beispiel hängt die Berechenbarkeit von f sowohl von der Funktion h als auch von der Funktion g ab.

f kann durchaus berechenbar sein, z.B. wenn für alle x gilt h(x) > 0.
Oder auch wenn g(x) = 0 für alle x mit h(x) = 0.

f kann aber auch nicht-berechenbar sein: Ist g zum Beispiel \(\omega\) und h die charakteristische Funktion des Halteproblems, dann ist f' mit f'(x) := f(x) + 1 die semi-charakteristische Funktion des Komplements des Halteproblems. Diese ist nicht berechenbar, denn das Komplement des Halteproblems ist nicht semi-entscheidbar. Also kann auch f nicht berechenbar sein, da sich f' mit einem Programm für f offensichtlich berechnen lässt.

[Christoph Walther]

Hi!

ich bin mir gerade unsicher, wenn ich z.b. die Funktionen g und h habe, g berechenbar und h nicht, ist dann folgendes Bsp. berechenbar?

Schauen Sie sich doch auch noch mal seite 31 im skript an - dort werden solche fälle diskutiert.

cw.

[CloneCommander]

Hallo, erst einmal vielen Dank für die ausführliche Antwort und den Tipp mit dem Skript, allerdings habe ich wohl meine Frage etwas "schwammig" formuliert und kam mit Seite 31 auch nicht direkt weiter. Ich glaube aber, ich habe jetzt eine Idee:

Oder auch wenn g(x) = 0 für alle x mit h(x) = 0.

Das heißt also, ich könnte f(x) = g(x) schreiben (und damit wäre f berechenbar, da auch g berechenbar), da wenn h(x) = 0 ist und der Fall "0" eintereten würde auch g(x) 0 ist? Also kann ch die Funktion sozusagen so ändern, dass h(x) nicht "gebraucht" wird?

[Christoph Walther]

Das heißt also, ich könnte f(x) = g(x) schreiben (und damit wäre f berechenbar, da auch g berechenbar), da wenn h(x) = 0 ist und der Fall "0" eintereten würde auch g(x) 0 ist? Also kann ch die Funktion sozusagen so ändern, dass h(x) nicht "gebraucht" wird?

Genauso ist es.

... und kam mit Seite 31 auch nicht direkt weiter.

Dort steht: "Generell gilt, daß eine Funktion mit einer Fallunterscheidung, die nicht abhängig von den Parametern der Funktion ist, auch dann berechenbar sein kann, wenn nicht algorithmisch festgestellt werden kann, welcher der Fälle zutrifft."

Und das ist in Ihrem beispiel genau der fall. Zugegebenermaßen etwas spitzfindig, denn die fallunterscheidung braucht man ja gar nicht. Aber trotzdem: Das zitat beschreibt den allgemeinen fall.

cw.

[CloneCommander]

Okay, dann wird jetzt alles etwas klarer - Danke!