Not logged in. · Lost password · Register

gabriel2029
Member since Nov 2018
37 posts
Subject: 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
arass
Member since Aug 2017
22 posts
"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.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen