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 8
Zur Aufgabe 3:
Ich bin von der Angabe bei der etwas verwirrt: Müsste (ich nenn die Vereinigung mal CTIME) CTIME nicht eine ECHTE Teilmenge von SPACE(0) sein?
Es gibt ja Turingmaschinen, die 0 zusätzlichen Platzbedarf haben, aber nicht in konstanter Zeit laufen (z.B. eine for-Schleife von i bis n mit leerem Körper hat lineare Laufzeit aber const Platzbedarf).
Ich hab die Aussage der Aufgabe jetzt so verstanden:
Wenn eine Turingmaschine konstant-Zeitbeschränkt ist, dann hat sie "gar nicht genug Zeit" um mehr Speicher anzufordern.Stimmt das so? Der Beweis sind ja dann nur ein, zwei Sätze…
Wo speicherst du dann die log_2 n bits des Zählers? Wenn die Anzahl Schleifendurchläufe von der Eingabe abhängt geht das gerade nicht ohne zusätzlichen Platzbedarf.
1 „Gefällt mir“
Ahh, stimmt! Dann eben eine Endlosschleife.
Es geht um eine Klasse von Entscheidungsproblemen, deine TM muss also immer terminieren 
Hallo,
ich hänge noch bei Aufgabe 1.2:
Meine Lösung für 1.1 (die ich jetzt nicht schreiben kann) erscheint mir recht schlüssig, allerdings weiß ich nicht, wieso das nicht auch für NP funktionieren sollte.
Ich suche nach irgendeinem Unterschied zwischen deterministischen und nicht-deterministischen Turingmaschinen, der mir hilft, den Ansatz für 1.1 zu verwerfen.
Kann mir jemand einen Hinweis oder Ansatz geben?
Bei einer deterministischen Turingmaschine könntest du den Ablauf (Zustände etc.) der Maschine nur mit der Eingabe “vorhersehen”, da eine deterministische Turingmaschine bei derselben Eingabe, mit denselben Schritten, dasselbe Ergebnis liefert.
Dies ist bei einer nicht-deterministischen Turingmaschine nicht der Fall. Heißt, dass eine nicht-deterministische Turingmaschine über (zBsp.) ganz andere Zustände zum Ergebnis kommen kann. Du kannst also ihren Ablauf nicht “vorhersehen”.
So hab ich es jedenfalls verstanden (und auch in der A1 eingesetzt).
Nochmal eine Frage zur drei:
Es klingt auf den ersten Blick recht logisch, aber könnte mir jemand mal ein, zwei Beispiele für Entscheidungsprobleme mit konstanter Zeit geben?
„In Zelle 3 steht eine 1.“
„Die Summe der ersten 5 Zellen ist kleiner als 42.“ (Hier ist die Abbildung auf SPACE(0) auch nicht völlig trivial, aber wenn du das hinbekommst, weißt du worauf’s ankommt.)
Oder ganz komplex:
„Akzeptiere.“
Ok, danke - auch wenn mir SPACE(0) bei dem zweiten Beispiel nicht ganz klar ist 
Aber was hindert mich denn daran, wenn ich z.B. bei “In Zelle 3 steht eine 1” noch munter währenddessen x Speicher belege - dass klappt doch auch in konstanter Zeit? Wo ist mein Denkfehler?
Das „was hindert dich“ ist genau der Punkt! Natürlich kannst du in jede TM jede Menge Mist einbauen, es geht aber um die Klasse von Problemen, die z.B. ohne zusätzlichen Speicher lösbar sind, und die veränderst du damit nicht. Du kannst dich natürlich blöd anstellen und sinnlos Speicher verwenden - das Problem an sich bleibt trotzdem auch ohne Speicher lösbar - und darauf kommt es bei Problemklassen an.
Ahh, klar 
Danke dir.
Aber so die Initialzündung für den Beweis fehlt mir doch noch ein wenig - noch ein Tipp vllt
Ich stehe echt bisschen auf dem Schlauch - kann mir jemand einen Denkanstoß geben, wie die Aufgabe 3 funktioniert?
Wie baust du eine Turingmaschine, die einfach 3 Schritte nach rechts läuft, und je nach Wert true oder false liefert? Irgendwie musst du da ja auch bis 3 „zählen“. Überleg dir am besten die Delta Tabelle und schau wo sich der Zähler versteckt.
Danke dir, etz hat’s geklingelt