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)
--- primitive Rekursion (http://www.informatikerboard.de/board/thread.php?threadid=70)

Geschrieben von Paul_H am 01.11.2006 um 15:00:

  primitive Rekursion

Tach,
ich soll zeigen, dass die Funktion max(x, y) primitiv rekursiv ist.
Mein Problem dabei ist, eine Fallunterscheidung zu vermeiden.
Irgendwo gibts hier einen Trick, den ich aber partout nicht sehen kann.

Ideen?
Gruß, Paul.


Geschrieben von Tobias am 01.11.2006 um 15:51:

 

Benutze eine Differenz auf [latex]\mathbb{N}[/latex] mit der Eigenschaft [latex]0 - x = 0 \; \forall x \in \mathbb{N}[/latex]. Die ist primitiv rekursiv (klar).

Dann kannst du max definieren durch:

[latex]max(x, y) = x + (y-x)[/latex]


Geschrieben von Paul_H am 01.11.2006 um 20:51:

 

ja genau.
Das ist es, vielen Dank.

Aber anzumerken, dass es sich hier um die modifizierte (nichtnegative) Differenz handeln muss.

Gruß, Paul.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH