Tilman
89 lines
2.8 KiB
PHP
89 lines
2.8 KiB
PHP
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
|
|
<link rel="stylesheet" type="text/css" media="all" href="stylesheet.css">
|
|
<title>Primitiv-rekursive Funktionen</title>
|
|
</head>
|
|
<body>
|
|
<span id="menu"><a href="index.php">zurück zur Liste</a></span>
|
|
|
|
<div id="buttons">
|
|
<form action="edit.php" method="POST">
|
|
<input type="hidden" name="filename" value="<?php echo $_SERVER['SCRIPT_FILENAME']?>">
|
|
<p>
|
|
<input type="submit" value="Seite bearbeiten">
|
|
</p>
|
|
</form>
|
|
</div>
|
|
|
|
<h1>Primitv rekursive Funktion</h1>
|
|
|
|
Jede berechenbare Funktion kann durch eine primitiv rekursive Funtkion mit Hilfe von einfachen Grundfunktionen dargestellt werden. <br><br>
|
|
<table>
|
|
<tr>
|
|
<td><b>Basisfunktionen</b></td>
|
|
<td>
|
|
clr () = 0<br>
|
|
suc (n) = n+1<br>
|
|
p (1, x<sub>1</sub>, x<sub>2</sub>, ... , x<sub>n</sub>) = x<sub>1</sub><br>
|
|
p (i, x<sub>1</sub>, x<sub>2</sub>, ... , x<sub>n</sub>) = p (i-1, x<sub>2</sub>, x<sub>3</sub>, ... , x<sub>n</sub>)
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
Zu einer k-stelligen Funktion <b>ψ</b> und einer (k+2)-stelligen Funktion <b>χ</b> ist eine (k+1)-stellige Funktion <b>φ</b> definiert.<br>
|
|
<b>φ</b> phi, <b>ψ</b> psi, <b>χ</b> chi ∈ PRF<br><br>
|
|
|
|
<b>φ</b> (0, x<sub>1</sub>, x<sub>2</sub>, ... , x<sub>n</sub>) = <b>ψ</b> (x<sub>1</sub>, x<sub>2</sub>, ... , x<sub>n</sub>)<br>
|
|
<b>φ</b> (y+1, x<sub>1</sub>, x<sub>2</sub>, ... , x<sub>n</sub>) = <b>χ</b> (φ (y, x<sub>1</sub>, x<sub>2</sub>, ... , x<sub>n</sub>), y, x<sub>1</sub>, x<sub>2</sub>, ... , x<sub>n</sub>)
|
|
|
|
<br><br>
|
|
|
|
<b>Verdeutlichung am Beispiel: Addieren und multiplizieren von zwei Zahlen</b><br>
|
|
<table>
|
|
<tr>
|
|
<td>
|
|
Aufstellen der Gleichungen →
|
|
</td>
|
|
<td>
|
|
Einfache Lösungen →
|
|
</td>
|
|
<td>
|
|
Gleichungen mit <b>ψ</b> und <b>χ</b>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<b>add</b> (0, m)<br>
|
|
<b>add</b> (n+1, m)
|
|
</td>
|
|
<td>
|
|
= m<br>
|
|
= suc (add (n, m))
|
|
</td>
|
|
<td>
|
|
= <b>p1</b> (m)<br>
|
|
= <b>suc (p1)</b> (add (n, m), n, m))
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<b>mul</b> (0, m)<br>
|
|
<b>mul</b> (n+1, m)
|
|
</td>
|
|
<td>
|
|
= 0<br>
|
|
= m + mul (n, m)
|
|
</td>
|
|
<td>
|
|
= <b>clr</b> (m)<br>
|
|
= <b>add (p1, p3)</b> (mult (n, m), n, m)
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
|
|
|
|
|
|
</body>
|
|
</html> |