Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | Wie funktioniert primitive Rekursion?

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Wie funktioniert primitive Rekursion? » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

[quote][i]Original von DH89[/i]
[b]Meine Frage:[/b]
Guten Tag zusammen,

ich bin Informatikstudent und beschäftige mich derzeit mit derBerechenbarkeit. Ein Thema dieser Berechenbarkeit ist die primitive Rekursion. Dabei hab ich aber ein paar Probleme.

Ich möchte eine Funktion min(y,x) = {1. y, falls y <= x oder 2. x, sonst} (Funktion hat logischerweise 2 Fälle) in primitiv rekursiver Schreibweise darstellen und weiß nicht so recht wie ich das machen soll.

Könnte mir da jemand helfen?

[b]Meine Ideen:[/b]
Die primitive Rekursion ist wie folgt induktiv definiert:

Basisfunktionen:
1. Konstante Funktionen sind Prim-Rek.
2. Alle Projektionen sind Prim-Rek.
3. Die Nachfolgerfunktion ist Prim-Rek.
Abschlusseigenschaften:
4. Komposition
5. Primitive Rekursion

Ich soll zeigen das die min-Funktion primitiv-rekursiv ist, also versucht man diese primitiv-rekursiv darzustellen oder man gibt ein LOOP-Programm an. Die Klasse der LOOP-Programme ist ja identisch zu der Klasse der primitiv-rekursiven Funktionen. Aber ein LOOP-Programm ist in dieser Aufgabe nicht erwünscht. Nur ein Beweis über einen primitiv-rekursiven Ausdruck und da hakt es halt bei mir :([/quote]

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Der letzte Beitrag

DH89

Wie funktioniert primitive Rekursion?

Meine Frage:
Guten Tag zusammen,

ich bin Informatikstudent und beschäftige mich derzeit mit derBerechenbarkeit. Ein Thema dieser Berechenbarkeit ist die primitive Rekursion. Dabei hab ich aber ein paar Probleme.

Ich möchte eine Funktion min(y,x) = {1. y, falls y <= x oder 2. x, sonst} (Funktion hat logischerweise 2 Fälle) in primitiv rekursiver Schreibweise darstellen und weiß nicht so recht wie ich das machen soll.

Könnte mir da jemand helfen?

Meine Ideen:
Die primitive Rekursion ist wie folgt induktiv definiert:

Basisfunktionen:
1. Konstante Funktionen sind Prim-Rek.
2. Alle Projektionen sind Prim-Rek.
3. Die Nachfolgerfunktion ist Prim-Rek.
Abschlusseigenschaften:
4. Komposition
5. Primitive Rekursion

Ich soll zeigen das die min-Funktion primitiv-rekursiv ist, also versucht man diese primitiv-rekursiv darzustellen oder man gibt ein LOOP-Programm an. Die Klasse der LOOP-Programme ist ja identisch zu der Klasse der primitiv-rekursiven Funktionen. Aber ein LOOP-Programm ist in dieser Aufgabe nicht erwünscht. Nur ein Beweis über einen primitiv-rekursiven Ausdruck und da hakt es halt bei mir unglücklich