Tilman
65 lines
2.6 KiB
PHP
65 lines
2.6 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>Das Lambda-Kalkül</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>Das λ-Kalkül - die kleinste Programmiersprache</h1>
|
|
<p>
|
|
Idee: 1900 stellt Hilbert die Frage nach der Existenz einem automatischen Verfahren, mit dem man alle Sätze der Mathematik beweisen kann.<br>
|
|
Turing und Church beweisen 1930, dass es ein solches Verfahren nicht gibt.<br>
|
|
Das λ-Kalkül bildet die mathematische Grundlage für funktionale Programmiersprachen.
|
|
</p>
|
|
<p style="font-family: monospace">
|
|
<name> := a | b | c | a1 | b2...<br>
|
|
<expression> := <name> | <function> | <application><br><br>
|
|
<function> := λ<name>.<expression><br>
|
|
<application> := <expression><expression>
|
|
</p>
|
|
<h2>Reduzieren von Ausdrücken:</h2>
|
|
<p style="font-family: monospace">
|
|
λx.x y → y<br>
|
|
(λx.xy)z → zy<br>
|
|
(λx.(λy.xy))ab → (λy.ay)b → ab
|
|
</p>
|
|
<h2>Zahlen</h2>
|
|
<p style="font-family: monospace">
|
|
0 ≡ λs(λz.z)<br>
|
|
1 ≡ λs(λz.s(z))<br>
|
|
2 ≡ λs(λz.s(s(z)))<br>
|
|
usw.
|
|
</p>
|
|
<h2>Funktionen</h2>
|
|
<p style="font-family: monospace">
|
|
Nachfolgefunktion:<br>
|
|
S ≡ λwyz.y(wyz)<br>
|
|
5S4 ≡ S(S(S(S(S(4))))) ≡ 9
|
|
<br><br>
|
|
True: T ≡ λxy.x<br>
|
|
False: F ≡ λxy.y<br>
|
|
<br>
|
|
And: ∧ ≡ λxy.xyF<br>
|
|
Or: &or ≡ λxy.xTy<br>
|
|
Not: ¬ ≡ λx.xFT
|
|
</p>
|
|
<h2>Links</h2>
|
|
<p>
|
|
<a href="http://www.betoerend.de/dasLandHinterDemEndeDesSinns/lambda/welcome.html">Das gefürchtete Lambda-Kalkül</a> - <b>Ist leider nicht mehr online! </b> Wer eine Kopie findet, bitte eintragen.<br>
|
|
<a href="http://de.wikipedia.org/wiki/Lambda-Notation">Kurze Wikipedia-Erläuterung zur Lambda-Notation</a>
|
|
</p>
|
|
|
|
</body>
|
|
</html> |