#

Brainfuck reloaded

Schon vor etlicher Zeit hatte mich mein Freund Toni auf die skurile Programmiersprache Brainfuck aufmerksam gemacht. Nun, auch mit meinem neuen Blog, wollte ich mich dem Thema etwas genauer widmen.

Die Skurilität von Brainfuck liegt nicht lediglich im Namen, sondern auch in der Grammatik der minimalistischen Programmiersprache, welche aus den acht Zeichen +,-, < ,>, ., ‚,‘, [ und ] besteht. Entsprechend kryptisch sieht dann ein Programm aus, woher Brainfuck auch seinen Namen hat und die Programme zur Kategorie „write once, read never“ gehören. Beispielsweise wird eine Multiplikation 2*3 durch folgenden Kode abgebildet:

++[->+++<]

Näheres zur Grammatik kann auf der folgenden Seite nachgelesen werden. Besonders praktisch ist die JavaScript Version mit Debugger.
Interessant ist Brainfuck vor allem für die theoretische Informatik. Denn bei Brainfuck handelt es sich um eine minimale Turing-Maschine. Alan M. Turing (1912 - 1954) hat die Existenz einer universellen Rechenmaschine, der Turing-Maschine, bewiesen, welche alle algorithmisch lösbaren Probleme berechnen und damit lösen kann. Die klassische abstrakte Turing-Maschine besteht aus folgenden Bestandteilen:

  • unendlich langes Speicherband
    eingeteilt in Zellen für je ein Zeichen eines
    Alphabets V {} (Leerzeichen, V)
  • Schreib-Lesekopf kann eine Zelle des Bandes lesen bzw.
    schreiben und jeweils um 1 Zelle nach links oder rechts
    bewegt werden
  • Steuerwerk mit einer endlichen Anzahl von Zuständen

  • Diese Regeln können durch eine minimale Programmiersprache zur Steuerung der Turing-Machine repräsentiert werden:

    Befehlsvorrat

  • clear name name := 0
  • incr name name := name + 1
  • decr name name := name � 1
  • while name not 0 do
    Anweisungsfolge
    end

  • Genau diese Befehle werden durch Brainfuck abgebildet, welches auch die Intention des Brainfuck Erfinders war. Tatsächlich existiert auch ein Beweis unter dem Titel "BF is Turing-complete".
    Meiner Meinung nach ist Brainfuck sehr gut dafür geeignet, Informatikstudenten die Turing-Maschine auf praktische Weise näher zu bringen.
    Anbei zwei sehr einfache Programme, die jeweils eine bestimmte Zahl berechnen:

    +++++++[->++[->+++<]<]

    ++++[->+++++<]>+++

    Besonders interessant finde ich die Frage, wie Programme minimal geschrieben werden können. Beispielsweise könnte man die Zahl 100 durch eine Folge von 100 '+' Symbolen darstellen. Eine kürzere Variante wäre es, eine Schleife zu schreiben, welche 10 mal 10 berechnet:

    ++++++++++[->++++++++++<]

    Eine Verkürzung der 10 z.B. durch 2*5 bringt keinen Erfolg:

    +++++[->++<][->++++++++++<]

    Nun ist die Frage, welche Form die kürzest mögliche ist.

    Tags:, , ,

    Leave a Reply »»

    Note: All comments are manually approved to avoid spam. So if your comment doesn't appear immediately, that's ok. Have patience, it can take some days until I have the time to approve my comments.