mikrocontroller.net

Forum: Offtopic Erklärung kleinster uni Turing-Maschine


Autor: Life Johnson (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

vielleicht hat ja der ein oder andere davon gehört, dass Wolfram den von 
ihm initiierten Wettbewerb zur Findung der kleinstmöglichen universellen 
Turing-maschine als erfolgreich beendet sieht. Ein Student darf sich 
über 25000$ Aufwandsentschädigung freuen.
http://www.heise.de/newsticker/meldung/97991

Der besagte Automat des Studenten kommt mit 3 Farben und 2 Zuständen 
aus. Vielleicht kann mir jemand helfen, die Überführungsfunktion in der 
Abbildung
http://www.heise.de/bilder/97991/0/0
zu interpretieren. Ich habe ein Verständnisproblem, da ich unweigerlich 
an die typischen eindimensionalen Automaten mit 2 Farben denken. siehe 
hier http://de.wikipedia.org/wiki/Zellul%C3%A4rer_Automat
Die Farben, schwarz und weiß, bilden hier die Zustände einer Zelle.
Aber wie ist die Grafik Wolframs zu verstehen?
Was stellen die kleinen Gnuppel dar.
Ist die Zustandüberführungsfunktion von Nachbarzellen abhängig, oder 
gibt es etwa gar keine Zellen?

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die "kleinen Gnubbel" stellen die zwei möglichen Zustände dar. Die 
Farben bilden hier das Alphabet.

Das linke Bild/die erste Regel würde ich etwa so interpretieren:
Wenn Zustand gleich "Gnubbelspitze oben" und Buchstabe an aktueller 
Position gleich "Orange", dann schreibe Buchstabe "Gelb", bewege Zeiger 
eine Position nach links und behalte den aktuellen Zustand 
("Gnubbelspitze oben") bei.

Das rechte Bild/die letzte Regel dann etwa so:
Wenn Zustand gleich "Gnubbelspitze unten" und Buchstabe an aktueller 
Position gleich "Weiß", dann schreibe Buchstabe "Orange", bewege Zeiger 
eine Position nach links und ändere den Zustand in "Gnubbelspitze oben"

Die restlichen halt analog.

CU

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Achso das Ganze natürlich ohne Gewähr. Hab mich bisher nicht wirklich 
mit Turingmaschinen befaßt sondern nur kurz den oben genannte Heise 
Artikel überflogen.

CU

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.