Seite 1 von 1

Brainfuck

Verfasst: Samstag 31. Mai 2008, 22:34
von Karl
Hiho.
Ich hab mir grad mal aus Spaß Brainfuck angeschaut.
Hier gibt's ja bestimmt n paar die das auch schonmal ausprobiert haben ;)
Ich hätte da mal eine Frage ...
Wenn ich jetzt, sagen wir mal die Zahl 4321 ausgeben möchte (bei 8-Bit), müsste ich dann etwa in jeden Byte die Ziffern 4 bzw 3 bzw 2 bzw 1 schreiben und diese dann nacheinander ausgeben?
Und kann man irgendwie die ASCII-Ausgabe ausschalten (IDE-Abhängig?), damit man anstatt den ASCII-Werten einfach Zahlen ausgespuckt bekommt? :o Wäre ja doof, wenn man für die Zahl 255 3 Bytes bräuchte, obwohl man diese ja in einem Byte darstellen kann. Bei 64 Bit wäre das ganze ja noch schlimmer, dann vergeudet man ja noch viel mehr Speicherplatz ;)

Verfasst: Samstag 31. Mai 2008, 22:44
von BlackJack
Du könntest Dir doch "einfach" in Brainfuck ein Unterprogramm schreiben, dass ein Byte in die Zeichenkettendarstellung umwandelt. :-)

Verfasst: Samstag 31. Mai 2008, 23:25
von Karl
BlackJack hat geschrieben:Du könntest Dir doch "einfach" in Brainfuck ein Unterprogramm schreiben, dass ein Byte in die Zeichenkettendarstellung umwandelt. :-)
import Unterprogramm? :D

Edit:
Und ist Brainfuck wirklich Turing-Vollständig?
Ich komm mir immer so eingeschränkt vor: "Hier hast du ein Array mit 30.000 Feldern, je 1 Byte, viel Spaß, mach damit was du willst!"
Nicht, dass ich je an diese Grenze gestoßen bin, aber wie kann man bitte innerhalb dieses Arrays zum Beispiel einen anderen Prozess beeinflussen?
Oder auf irgendwelche anderen Mittel als die Outputkonsole zurückgreifen? Zum Beispiel eine GUI in Brainfuck schreiben? Ja okay, das ist vielleicht nahezu unmöglich, weil zu kompliziert in Brainfuck, aber geht das denn rein theoretisch überhaupt?
Dass es mit 30.000 Feldern je ein Byte nicht Turing-Vollständig sein kann, ist eh klar, aber ich denke mal, es sollte kein Problem darstellen, diese auf "unendlich viele" zu erweitern.

Verfasst: Sonntag 1. Juni 2008, 06:40
von Leonidas
Karl hat geschrieben:Und ist Brainfuck wirklich Turing-Vollständig?
Ich komm mir immer so eingeschränkt vor: "Hier hast du ein Array mit 30.000 Feldern, je 1 Byte, viel Spaß, mach damit was du willst!"
Nicht, dass ich je an diese Grenze gestoßen bin, aber wie kann man bitte innerhalb dieses Arrays zum Beispiel einen anderen Prozess beeinflussen?
Letztendlich muss du bedenken dass dein Speicher auch nur eine begrenzte Anzahl Speicherzellen hat. Kannst du Prozesse forken? Hast du eine GUI?

Verfasst: Sonntag 1. Juni 2008, 08:29
von BlackJack
@Karl: Ob eine Sprache Turingvollständig ist, hängt davon ab, ob die Sprache und eine Turingmaschine gleichmächtig sind. Also ob man die Sprache mit einer Turingmaschine simulieren kann und ob eine Turingmaschine die Sprache simulieren kann.

Die Frage die sich stellt ist also, ob man in Brainfuck eine Turingmaschine simulieren kann. Die Antwort sollte ja sein.

Verfasst: Sonntag 1. Juni 2008, 08:51
von sma
BF mit einer unbegrenzten aber endlichen Anzahl von Zellen ist Turingvollständig. Hier noch ein bisschen Theorie...

Stefan

Verfasst: Sonntag 1. Juni 2008, 11:48
von Karl
BlackJack hat geschrieben:@Karl: Ob eine Sprache Turingvollständig ist, hängt davon ab, ob die Sprache und eine Turingmaschine gleichmächtig sind. Also ob man die Sprache mit einer Turingmaschine simulieren kann und ob eine Turingmaschine die Sprache simulieren kann.

Die Frage die sich stellt ist also, ob man in Brainfuck eine Turingmaschine simulieren kann. Die Antwort sollte ja sein.
Dafür gibt's irgendwo Beweise, aber ich hab ehrlich gesagt keine Lust, das zu überprüfen :)
BlackJack hat geschrieben:BF mit einer unbegrenzten aber endlichen Anzahl von Zellen ist Turingvollständig. Hier noch ein bisschen Theorie...
Okay, das klingt so weit logisch ...
Also kann Brainfuck im Prinzip alles. Aber ich kann mir eben nicht vorstellen, dass Brainfuck eine GUI erzeugen kann. Oder andere Programme z.B. beenden kann.
Das ganze spielt sich doch in irgendeinem Array ab, welches man verändern kann, mehr nicht oO
Oder gehört das nicht dazu, um Turingvollständig zu sein? (Oder eher anders gesagt, es müsste daraus folgen)
Vielleicht hab ich einfach ne falsche Vorstellung davon.

Verfasst: Sonntag 1. Juni 2008, 12:28
von BlackJack
Was denkst Du denn was zum Beispiel Maschinenprogramme auf Deinem Rechner sind!? Das ist letztlich pro Prozess doch auch bloss ein grosses Array, wo der Prozessor die Maschine spielt und Zahlen als Befehle und Werte interpretiert.

Und C ist auch Turingvollständig und trotzdem kann man damit auf x86-Plattformen (fast) keine Hardware ansprechen oder komplette Betriebssysteme schreiben! Denn C bietet weder die Möglichkeit auf "Prozessorports" zu zu greifen, noch Unterbrecherbehandlung zu implementieren. Dazu muss man auf Assembler aus weichen.

Andererseits kannst Du in Brainfuck Pixelbilder im Array ablegen und die manipulieren. Wenn Du also eine Hardware hättest, die BF direkt ausführen kann, einen Bereich des Speichers als Framebuffer auffasst und den Zustand von Geräten wie Tastatur und Maus an festen Stellen in den Speicher einblendet, kann man auch in BF "problemlos" eine GUI schreiben.

Turingvollständigkeit hat etwas mit Berechenbarkeit zu tun und nicht, ob es eine Schnittstelle zu beliebiger Hardware gibt.

Verfasst: Sonntag 1. Juni 2008, 12:39
von Karl
BlackJack hat geschrieben:Was denkst Du denn was zum Beispiel Maschinenprogramme auf Deinem Rechner sind!? Das ist letztlich pro Prozess doch auch bloss ein grosses Array, wo der Prozessor die Maschine spielt und Zahlen als Befehle und Werte interpretiert.

Und C ist auch Turingvollständig und trotzdem kann man damit auf x86-Plattformen (fast) keine Hardware ansprechen oder komplette Betriebssysteme schreiben! Denn C bietet weder die Möglichkeit auf "Prozessorports" zu zu greifen, noch Unterbrecherbehandlung zu implementieren. Dazu muss man auf Assembler aus weichen.

Andererseits kannst Du in Brainfuck Pixelbilder im Array ablegen und die manipulieren. Wenn Du also eine Hardware hättest, die BF direkt ausführen kann, einen Bereich des Speichers als Framebuffer auffasst und den Zustand von Geräten wie Tastatur und Maus an festen Stellen in den Speicher einblendet, kann man auch in BF "problemlos" eine GUI schreiben.

Turingvollständigkeit hat etwas mit Berechenbarkeit zu tun und nicht, ob es eine Schnittstelle zu beliebiger Hardware gibt.
Okay, ich wusste nur nicht, dass man dazu spezielle Hardware bräuchte.
Also kann Brainfuck eigentlich alles, ist aber nur vom System abgetrennt?
Okay, also kann man mit Brainfuck nicht zum Beispiel andere Prozesse beeinflussen, weil es nur inerhalb seines eigenen Speicherbereiches arbeiten kann? Das fände ich nämlich interessant, hätte man was lernen können :p Oder auch was kaputtmachen.
Genau das wollte ich nämlich eigentlich wissen. Ob man mit Brainfuck alles machen kann, oder eben nicht. Und da hab ich eben aus Unwissen heraus etwas mit Turingvollständigkeit verwechselt.
Ich dachte Turingvollständig = kann alles ;)
Aber es kann eben nicht alles, da die entsprechende Schnittstelle zur Hardware fehlt, weshalb es so ziemlich gar nichts kann. Beziehungsweise es kann theoretisch alles berechnen aber das Errechnete müsste dann von einem anderem Programm ausgeführt werden.
Ich hab mich eben gewundert: Es ist Turingvollständig aber ich kann damit keine GUI programmieren? Ich hab mich gefragt, wie man sowas machen soll, wenn man nicht aus seinem Array rauskommt :)
Aber okay, jetzt ist alles klar, dank deinem erhellendem Beitrag.

PS: Gibt's keine Freaks die schon eine entsprechende Schnittstelle programmiert haben oder so? :o

Verfasst: Sonntag 1. Juni 2008, 16:44
von Leonidas
BlackJack hat geschrieben:Wenn Du also eine Hardware hättest, die BF direkt ausführen kann, einen Bereich des Speichers als Framebuffer auffasst und den Zustand von Geräten wie Tastatur und Maus an festen Stellen in den Speicher einblendet, kann man auch in BF "problemlos" eine GUI schreiben.
Für Brainfuck gibt es sowas nicht, aber LispM kommt dem schon recht nahe.