Turingmaschine
-
Hallo, kann mir wer sagen was eine Turingmaschine ist? Der Wikipedia Text dazu hat mich nur verwirrt. Wie sähe sowas unter C aus?
lg tajla
-
Eine Turing-Maschine ist ein recht abstraktes Maschinenkonzept - das nicht sehr viel Ähnlichkeit mit einem handelsüblichen PC hat. Das in C umzusetzen wird etwas schwierig.
Vereinfacht gesprochen besteht die Turingmaschine aus einem (unendlich langen) Band, auf dem Zeichen aufgedruckt werden können, einem Register (für den aktuellen Zustand), einem Schreib-Lese-Kopf und einer Tabelle. Der Ablauf ist ungefähr so:
-
lies den Inhalt 'x' der aktuellen Bandzelle
-
lies den Inhalt des Registers 'n'
-
schau in der Tabelle in Zeile 'n'/Spalte 'x' nach und arbeite deren Inhalt ab:
-
schreibe einen neuen Wert aufs Band
-
bewege das Band nach links oder rechts (oder bleib stehen)
-
trage einen neuen Wert ins Register ein
oder
- halte an
- gehe zurück zu 1
(es gibt verschiedene Variationen, aber alle lassen sich zurückführen auf die binäre Ein-Band-Maschine (auf dem Band stehen nur Nullen und Einsen) mit entsprechend vielen möglichen Zuständen)
In der verwendeten Tabelle steht das eigentliche Programm - und das kann alles mögliche darstellen.
-
-
tajla schrieb:
Hallo, kann mir wer sagen was eine Turingmaschine ist? Der Wikipedia Text dazu hat mich nur verwirrt. Wie sähe sowas unter C aus?
lg tajla
Eine Turingmaschine versuchen zu simulieren macht keinen Sinn (es gibt einige Programme und bestimmt auch offene Quellcodes mit einer Simulation davon - und vielleicht sogar Compiler die C-Code in Turingmaschinen-Befehle umsetzen).
Die Turingmaschine wird in der theoretischen Informatik nur eingeführt um von konkreter Hardware unabhängig zu sein. Im speziellen geht es darum zu beweisen welche Probleme prinzipiell mit einer Turingmaschine gelöst/berechenbar sind und welche nicht (z. B.: Kann eine Bestimme Sprache von einem Automaten erkannt werden? Die Ergebnisse sind z. B. interessant für die Compilerentwicklung).
-
mir fällt da spontan mal Brainfuck ein... das ist ne programmiersprache, die recht ähnlich funktioniert, wiedas was CStoll beschreiben hat... (der name ist allerdings programm... Für programmiere denen das Sodoku ausgegangen ist^^)