Frage zur Berechenbarkeit, wenn h im "if" steht

CloneCommander
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 19. Dez 2005 09:07
Wohnort: Maintal
Kontaktdaten:

Frage zur Berechenbarkeit, wenn h im "if" steht

Beitrag von 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
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Beitrag von 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
Dozentin/Dozent
Beiträge: 86
Registriert: 1. Nov 2005 18:51

Re: Frage zur Berechenbarkeit, wenn h im "if" steh

Beitrag von Christoph Walther »

CloneCommander hat geschrieben: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
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 19. Dez 2005 09:07
Wohnort: Maintal
Kontaktdaten:

Beitrag von 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:
Simon Siegler hat geschrieben: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
Dozentin/Dozent
Beiträge: 86
Registriert: 1. Nov 2005 18:51

Beitrag von Christoph Walther »

CloneCommander hat geschrieben: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.
CloneCommander hat geschrieben:... 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
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 19. Dez 2005 09:07
Wohnort: Maintal
Kontaktdaten:

Beitrag von CloneCommander »

Okay, dann wird jetzt alles etwas klarer - Danke!

Antworten

Zurück zu „Archiv“