nicht angemeldet
Hallo Ferby,
da es bisher noch niemand getan hat, erst mal eine Beschreibung einer Turingmaschine
Eine Turingmaschine besteht aus einem unendlich langen Speicherband, mit einem Lese/Schreibkopf, das Anfangs mit Leerzeichen beschrieben ist, einem Startzustand, einer Zustandübergangsfunktion sowie einer Menge zulässiger Bandzeichen und Zustände.
Die Maschine liest nun immer das Zeichen, über dem der Lese/Schreibkopf steht und guckt in einer Tabelle (Zustandsübergangsfunktion) unter dem aktuellen Zustand und dem gelesenen Zeichen nacht, was der nächste Zustand ist, welches Zeichen auf das Band geschreiben wird, ob der Kopf
nach links oder rechts bewegt wird und ob die Rechnung beendet ist.
Die Eingabe wird anfangs auf das Band geschrieben, die Ausgabe steht hinterher auf dem Band.
Eine Sprache ist Turingvollstängig gdw man mit ihr ein Programm schreiben kann, dass eine beliebige Turingmaschine einliest und ausführt
Ich bin mir nicht sicher, ob sie auch von einer Turingmaschine interpretiert werden können muss. Da man aber annimmt, dass es keine Algorithmusdefinition gibt, die mächtiger ist, als die Turingmaschine, ist das nicht so entscheidend.
Grüße
Daniel