Javakurs/Übungsaufgaben/Brainfuck
Inhaltsverzeichnis
Einführung
Java ist eine komplexe und mächtige Programmiersprache mit der man viele informatische Probleme lösen kann. Doch wie weit kann man den Befehlssatz einer Sprache reduzieren ohne das diese die Eigenschaft verliert, beliebige mathematische Probleme zu lösen? Diese spezielle Eigenschaft wird Turingkomplettheit genannt. Alle Programmiersprachen sind für gewöhnlich turingkomplett, was bedeutet, dass sie jedes berechenbare Problem lösen können. Zu diesen Problemen zählen zum Beispiel sämtliche mathematische Probleme, aber auch Probleme die eher struktureller Natur sind, also auch das Suchen von Einträgen in einer Kontaktliste (nein, der Weltfrieden ist leider nicht berechenbar).
Brainfuck ist eine Programmiersprache, die ebenfalls turingkomplett ist, allerdings nur aus acht Befehlen besteht. In dieser Aufgabe könnt ihr selbst einen auf einer Turingmaschine basierten Interpreter für eine eigene kleine Sprache schreiben, die man in einen weiteren Schritt Brainfuck-kompatibel machen kann und damit auch turingkomplett.
Aufgabenstellung
In dieser Aufgabe bauen wir uns eine simple Turingmaschine, welche vorgegebenen Programmcode einer eigenen Sprache lesen und auswerten soll. Die Turingmaschine besitzt dabei nur ein Arbeitsband (workingTape) der Länge 10. Es existiert ein Lese/Schreibe-Kopf (head), der über das workingTape gleiten kann, dort Werte ändern und Werte ausgeben soll. Bewegt sich der Kopf über ein Ende des Arbeitsbandes hinaus, so taucht er auf der anderen Seite wieder auf (wenn also z.B der head von Feld 10 auf das 11. Feld bewegt wird, dann soll er wieder auf das 1. zeigen).
Die Maschine selbst wird durch einen einfachen Programmcode gesteuert, der aus 5 Befehlen besteht:
- > Dieser Befehl bewegt den head ein Feld nach rechts
- < Dieser Befehl bewegt den head ein Feld nach links
- + Dieser Befehl erhöht den Wert des aktuellen Feldes um 1
- - Dieser Befehl verringert den Wert aktuelles Feldes um 1
- # Dieser Befehl gibt den aktuellen Wert auf der Konsole aus
Der Programmcode der die Turingmaschine steuert, soll in einem Array namens sourceCode stehen, der Code soll Schritt für Schritt durchgegangen und ausgeführt werden. Auf dem Arbeitsband werden Werte vom Typ char gespeichert, die anfangs alle den Wert 'a' haben. Der head zeigt am Anfang auf das erste Feld auf dem workingTape.
Hinweis 1: char-Werte werden intern als Zahlenwerte gespeichert, deshalb könnt ihr ohne Probleme sowas wie char example = 'a'+1; schreiben. Wenn ihr wissen wollt, welche Zeichen durch welche Zahlen repräsentiert werden, dann schaut in die ASCII-Tabelle.
Jetzt solltet ihr auch in der Lage sein, mit eurer eigenen Turingmaschine ein "Hello World"-Programm zu schreiben. Wenn ihr eure Turingmaschine eigentständig erweitern wollt, dann schaut euch die Sprache Brainfuck an. Brainfuck ist eine Programmiersprache, welche ähnlich arbeitet wie unsere Turingmaschine in dieser Aufgabe.
Hinweis 2: Zum Testen verwendet einfach diese Initialisierung der Variable Source-Code. Wenn ihr alles richtig gemacht habt, dann sollten die Buchstaben a, b und c ausgegeben werden. Die Schreibweise mit den geschweiften Klammern und den Kommawerten legt automatisch ein Array an und füllt es mit den beschriebenen Werten (Deklaration & Initialisierung in einem Schritt):
char[] sourceCode = {'#', '+', '#', '+', '#'};
Kommentare
Wenn du Anmerkungen zur Aufgabe hast oder Lob und Kritik loswerden möchtest, ist hier die richtige Stelle dafür. Klicke einfach ganz rechts auf "bearbeiten" und schreibe deinen Kommentar direkt ins Wiki. Keine Scheu, es geht nichts kaputt ;)
FehlerKategorie
Um den Char um einen Wert zu erhöhen müsst ihr eure Variable zurück casten.
char Example = (char)('a'-1);
Das stimmt nicht man kann auch das schreiben:
char Example = 'a' - 1;
Sorry wenn ich das so schreibe, aber das ist die erste Aufgabenstellung wo sich mir der Hintegrund, bzw. der Sinn nicht wirklich erschliesst, wäre jemand der das verstanden hat so freundlich das ganze ein wenig mehr zu erläutern? Das wäre ultranett :>. -mw-
Fehler in NetBeans:
workingTape[head]=workingTape[head]+1;
funktioniert nicht! man muss explizit casten:
workingTape[head]=(char)(workingTape[head]+1);
Mit javac dagegen funktionierts.
