www.AlgorithMan.de
Where theory comes alive
Kontextfreie Grammatiken
Ich habe 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.
41 KiB
Ein kleiner Interpreter für die minimalistische, aber Turing-vollständige "Programmiersprache" GOTO.
40 KiB
Ein kleiner Interpreter für die minimalistische und NICHT Turing-vollständige "Programmiersprache" LOOP. LOOP ist äquivalent zu primitiver Rekursion (siehe μ-Rekursion)
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.tm" 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.