Frage zur Reduktion der leeren Menge...

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

Frage zur Reduktion der leeren Menge...

Beitrag von CloneCommander »

Hallo!

Ich habe ein Frage bezüglich der Reduktion:

Angenommen, ich habe IN <f {} ({} = leere Menge und IN = nat. Zahlen)
Dann muss es eine Funktion geben für die gilt: m € IN <=> f(m) € {}

Mir hat nun jemand gesagt, die Funktion solle total und berechenbar sein - CYCLE würde also nicht funktionieren und die Aussage wäre Blödsinn.

Im Script habe ich allerdings nur gesehen, dass sie berechenbar sein soll. Also könnte ich f = CYCLE angeben und es würde funktionieren?

MfG CC

jak
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 11. Nov 2004 15:42
Kontaktdaten:

Beitrag von jak »

naja... m ist immer eine natuerliche Zahl, also hast du links eine 1 stehen
f(m) ist nie in {} drin, d.h. du hast rechts eine 0 stehen, damit hast du dann

1 <=> 0, d.h. die Annahme, dass es (ueberhaupt) eine Funktion gibt ist falsch, die Aufgabe muesste also heissen :fur alle Probleme --ausser dem leeren Problem-- gilt IN <f M, denn fuer das leere Problem gilt das nicht.

CYCLE ist insbesondere berechenbar!! es ist eben eine partiell definierte funktione, aber CYCLE ist ja ein P-Programm --> ist also auch berechenbar!

jak

Christoph Walther
Dozentin/Dozent
Beiträge: 86
Registriert: 1. Nov 2005 18:51

Re: Frage zur Reduktion der leeren Menge...

Beitrag von Christoph Walther »

CloneCommander hat geschrieben:Mir hat nun jemand gesagt, die Funktion solle total und berechenbar sein
'Jemand' hat recht - für die reduktionsfunktion fordert man 'berechenbar' und 'total'. Das skript ist hier fehlerhaft (sorry) & muß diesbzgl. korrigiert werden.

cw.

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Beitrag von Simon Siegler »

Das Skript ist diesbezüglich nicht fehlerhaft, die Totalität ist nur sehr gut in der Notation versteckt. Der Pfeil ohne Balken am linken Ende (\rightarrow) steht für totale, der mit Balken (\mapsto) für allgemeine Funktionen (vergleiche Kapitel 13). Leider rendert das Forum \mapsto als \rightarrow.

Mit freundlichem Gruß,
Simon Siegler

Antworten

Zurück zu „Archiv“