Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Blatt 7
Bei der Aufgabe 2 geht es ja darum eine Registermaschine auf einer Turingmaschine zu simulieren und den store Befehl S[R_i] = R_j nachzubilden. So eine Zuweisung ist eigentlich nicht schwer auf einer Turingmaschine zu simulieren, was genau bedeutet aber das S in Zusammenhang der Register? In Aufgabe 1 kam der Code S vor, ist das hier wieder der Fall?
S ist nach Definition der RAM einfach deren Speicher, S[R_i] ist also die Speicherzelle mit Index R_i.
1 „Gefällt mir“
Ok danke 
Ich habe im moment noch meine Probelme mit Aufgabe 3.
Wenn ich die Zeitkonstruierbarkeit richtig verstanden habe, muss ich ja im ersten Teil der Aufgabe eine Turingmaschine finden, die bei einer Eingabe der Länge n in c*n Schritten bin(n) auf das Ausgabeband schreibt.
Allerdings brauche ich bei meinen Ansätzen bisher mehr als lineare Zeit.
Hat jemand vllt einen Tipp, der mich in die richtige Richtung lenken könnte?
Mir ist bisher zur Aufgabe 3 auch nur die Idee gekommen die Länge der Eingabe einfach abzuzählen und damit einen Counter hochzuzählen, das brauch aber n*log(n).
Bin auch etwas ratlos :huh:
Die einzige Möglichkeit die mir einfällt wäre unäres hochzählen, sprich ne Strichliste zu führen für jedes Zeichen ungleich Blank eine 1 aufs Ausgabeband, aber hier ist ja binär gefordert. Need hälp!
War bei Aufgabe 3 auch gehangen. Bis ich in der Mitschrift die “amortisierte Laufzeitanalyse des binären Zählers” gefunden hab. Darin haben wir eine Laufzeit von O(n) nachgewiesen… Damit wars dann ganz gut machbar 
Dann ist es natürlich einfach 