www.AlgorithMan.de
where theory comes alive
Kontextfreie Grammatiken
Ich have auch eine Klasse für Kontextfreie Grammatiken, die u.A. einen Parsergenerator für LL(1)-Grammatiken enthält. Die Klasse ist z.Z. aber Work-In-Progress.
49 KiB
Ein Beweis dafür, dass im reinen λ-Kalkül alle Primitiv-Rekursiven Funktionen ohne Fixpunkt Kombinator berechenbar sind.
Fixpunkt-Kombinatoren sind insofern äquivalent zum μ-Operator aus den μ-rekursiven Funktionen... Und das passt hervorragend dazu, dass μ auch den kleinsten Fixpunkt einer Funktion bezeichnet... das passt sogar so gut, dass ich das für keinen Zufall halte. Ähnliche Gedankengänge dürften sich bei Church, Turing, Kleene & Co. abgespielt haben.

Kleenes Normalform-Theorem (siehe auch Kapitel 2.9 im Skript Rekursionstheorie) kann man somit auf den reinen λ-Kalkül übertragen: Jede berechenbare Funktion ist darstellbar durch einen λ-Term, der höchstens einen Fixpunkt-Kombinator enthält.
Hier ist der LaTeX Quellcode.
34 KiB
In der Vorlesung Compilerbau (Skript) entwickelt man im Laufe des Semesters Compiler, die BPS (Beispiel-ProgrammierSprache) Quellcodes übersetzen in Zwischencode für die Abstrakten Maschinen AM und ZPP.
Damit man die generierten Codes nicht nur angucken und ihre Korrektheit nachrechnen kann, habe ich diese virtuelle Maschine für AM entwickelt, damit man seine generierten Codes auch in Aktion sehen kann.
48 KiB
In der Vorlesung Compilerbau (Skript) entwickelt man im Laufe des Semesters Compiler, die BPS (Beispiel-ProgrammierSprache) Quellcodes übersetzen in Zwischencode für die Abstrakten Maschinen AM und ZPP.
Damit man die generierten Codes nicht nur angucken und ihre Korrektheit nachrechnen kann, habe ich diese virtuelle Maschine für ZPP entwickelt, damit man seine generierten Codes auch in Aktion sehen kann.
107 KiB
Ein Compiler, der "Beispiel Programmier Sprachen" Quellcodes (siehe Vorlesung Compilerbau und Skript) in die Zwischencode-Ebene "AM" (Abstract Machine) übersetzt.

Weiter unten findet sich eine virtuelle Maschine für AM, in der man die generierten Codes laufen lassen kann.
18 KiB
Ein kleiner Interpreter für die minimalistische, aber Turing-vollständige "Programmiersprache" GOTO.

Hier ist ein (WebAssembly-basiertes) Web-Interface dafür.

8 KiB
Ein Assembler zusammen mit einer Multitasking-fähigen Virtuellen Maschine - geschrieben in JavaScript.
40 KiB
Ein kleiner Interpreter für die minimalistische und NICHT Turing-vollständige "Programmiersprache" LOOP.
21 KiB
Ein kleiner Interpreter für die Turing-vollständige, mathematische "Programmiersprache" μ-Rekursion.

Hier ist ein (WebAssembly-basiertes) Web-Interface dafür.

Das ist eine ziemlich krasse Beschränkung auf nichts Anderes als Funktionen. Im Gegensatz zum λ-Kalkül werden die Funktionen aber nicht explizit aufeinander angewendet, sondern sie werden mit Komposition, primitiver Rekursion und μ-Rekursion miteinander kombiniert.

Diese Programmiersprache ist ziemlich verwirrend. Ich finde dieses Skript sehr hilfreich.
43 KiB
Eine funktionale Programmiersprache, die den reinen λ-Kalkül benutzt. Das ist eine ziemlich krasse Beschränkung auf nichts Anderes als Funktionen - nichteinmal Zahlen oder Vergleiche sind erlaubt. Trotzdem ist der Kalkül Turing vollständig, wie ich auch in der beiliegenden PDF Datei beweise (neben einer Anleitung, wie man mit dem Programm arbeitet und wie die ganzen standard-Funktionen funktionieren).

Hier ist ein (WebAssembly-basiertes) Web-Interface dafür.
51 KiB
Ein Programm, das Turingmaschinen simuliert.
Die beiliegenden Beispielprogramme "un2bin.tm" und "fast_un2bin.tm" rechnen eine Unäre Zahl in ihre Binärdarstellung um, "bin_addition.tm" addiert zwei Binärzahlen. Das Programm "minsky_univ" ist eine Implementierung von M.L. Minskys Universeller Turingmaschine von 1967 und minsky_multi simuliert zwei Turingmaschinen parallel.

Dank Cygwin ist auch eine Version für Windows enthalten.
40 KiB
Ein kleiner Interpreter für die minimalistische, aber Turing-vollständige "Programmiersprache" WHILE.