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.
Fragen zur Aufgabe A17 (und A20)
Hallo,
zur Aufgabe A17: Bedeutet “verliert”, woher der Faktor s(n) bei der Simulation der universellen 2-Band-Turingmaschine auf einer 1-Band-Turingmaschine nach dem Verfahren in der Vorlesung kommt? Außerdem: Wie genau muss man diese Aufgabe, insbesondere Teilaufgabe b) beschreiben. Die Aufgabenstellung besagt: “[…] Sie brauchen sich insgesamt keine neue Simulation auszudenken, um — als das Ergebnis dieser Aufgabe — eine universelle […]”. Heißt das, dass man nur den entscheidenden “Gag”, den man braucht, um die Laufzeit zu reduzieren, beschreiben muss, oder, dass man sich wieder eine Simulationsbeschreibung, wie in der Vorlesung vorgestellt wurde, ausdenken muss. Insbesondere wird uns nicht klar, was mit “man soll sich insgesamt keine neue Simulation ausdenken” gemeint ist, ob nicht eine Anmerkung, was geändert werden muss, ausreicht oder gar die Simulation neu geschrieben werden muss, indem man die bisherige Simulation überarbeitet.
Reicht es bei der A20, eine Turingmaschine mit einem Pseudocode, ähnlich wie in der Vorlesung, zu beschreiben.
LG Gabriel
“verlieren” bedeutet in dem Zusammenhang warum der Faktor s(n) auf die Laufzeit ( t(n) ) noch hinzu kommt.
Also, warum haben wir anstelle der Laufzeit t(n) für die 2-Band TM nun mit der 1-Band TM eine Laufzeit der Simulation von t(n)*s(n)?
zu b) Sie brauchen keine komplett neue Simulation angeben, es reicht hier die nötigen Modifikationen anzugeben, um auch mit der 1-Band TM eine Laufzeit von t(n) zu erhalten.
zu A20:
Ja Pseudocode reicht an der Stelle aus. Achten Sie aber darauf, dass Turingmaschinen als Eingabe keine Zahlen sondern 0-1-Folgen bekommen.