joho
Grünschnabel
Dabei seit: 21.01.2017
Beiträge: 4
|
|
Hallo allerseits
,
ich hänge bei dem Beweis der PSPACE-vollständigkeit der Sprache:
Turingmaschine , die das Wort akzeptiert und dabei höchstens Bandzellen besucht
1. Reicht es um zu zeigen, dass , wenn eine universelle TM konstruiert wird, welche simuliert, aber nach spätestens Schritten stoppt, falls M nicht vorher terminiert?
2. Für den Beweis, dass auch ist, muss ich auf ein anderes Problem aus reduzieren?
und genau bei 2. stehe ich echt auf dem Schlauch.
Schon mal vielen Dank im voraus
|
|