Kontextfreie Grammatiken,
die u.A. einen Parsergenerator für
LL(1)-Grammatiken enthält.
Die Klasse ist z.Z. aber Work-In-Progress.
Ich habe auch eine Klasse für
Eine Virtuelle Maschine,
die die
Breadboard-CPU
von Ben Eater simuliert.
Man kann ein Programm Byte-für-Byte direkt in den RAM schreiben und den Instruction Pointer setzen. Man kann das Programm aber auch oben einfügen und Laden.
Einen dazu passenden Assembler habe ich auch geschrieben.
Man kann ein Programm Byte-für-Byte direkt in den RAM schreiben und den Instruction Pointer setzen. Man kann das Programm aber auch oben einfügen und Laden.
Einen dazu passenden Assembler habe ich auch geschrieben.
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.
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.
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.
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.
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.
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.
LOOP ist äquivalent zu primitiver Rekursion (siehe μ-Rekursion)
Ein Interpreter
für die Turing-vollständige,
mathematische "Programmiersprache"
μ-Rekursion.
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 verzahnt.
Diese Programmiersprache ist ziemlich verwirrend. Ich finde dieses Skript sehr hilfreich. Hier ist der Quellcode.
Diese Programmiersprache ist ziemlich verwirrend. Ich finde dieses Skript sehr hilfreich. Hier ist der Quellcode.
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.
Hier ist der Quellcode. Mit dabei ist auch eine PDF Datei, in der ich die Turing-Vollständigkeit beweise und eine Anleitung, wie man mit dem Kalkül arbeitet und wie die ganzen standard-Funktionen funktionieren.
Hier ist der Quellcode. Mit dabei ist auch eine PDF Datei, in der ich die Turing-Vollständigkeit beweise und eine Anleitung, wie man mit dem Kalkül arbeitet und wie die ganzen standard-Funktionen funktionieren.
Ein SAT-Solver.
Der Algorithmus ist im Kern noch recht schlicht gehalten - mein Haupt-Ziel ist (vorerst)
nicht, an Weltmeisterschaften teilzunehmen,
sondern einen einigermaßen brauchbaren SAT-Solver zu haben, der vor allem leicht zu bedienen
ist.
Die Meisten SAT-Solver verlangen nämlich Eingaben im DIMACS Format, d.h. die Formeln müssen in Konjunktiver Normalform sein und Variablen dürfen keine alphanumerischen Namen haben, sondern müssen mit Zahlen bezeichnet werden.
Mein SAT-Solver erlaubt alphanumerische Variablen-Namen, die auch bei der Ausgabe des Ergebnisses verwendet werden. Außerdem können diverse operatoren und Verschachtelungen benutzt werden. Eine Konjunktive Normalform wird im Zwischenschritt automatisch erzeugt.
Hier ist der Quellcode.
Die Meisten SAT-Solver verlangen nämlich Eingaben im DIMACS Format, d.h. die Formeln müssen in Konjunktiver Normalform sein und Variablen dürfen keine alphanumerischen Namen haben, sondern müssen mit Zahlen bezeichnet werden.
Mein SAT-Solver erlaubt alphanumerische Variablen-Namen, die auch bei der Ausgabe des Ergebnisses verwendet werden. Außerdem können diverse operatoren und Verschachtelungen benutzt werden. Eine Konjunktive Normalform wird im Zwischenschritt automatisch erzeugt.
Hier ist der Quellcode.
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.
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.