Was bedeutet sublinearer Raum für Turingmaschinen?

Es hat sich gezeigt, dass das Problem der Entscheidung, ob eine Eingabe ein Palindrom ist oder nicht, Speicherplatz auf einer Turing-Maschine erfordert . Selbst das Speichern der Eingabe benötigt jedoch Speicherplatz  Bedeutet dies nicht, dass alle Turing-Maschinen Speicherplatz benötigen ?$\Omega(\log n)$$n$$\Omega(n)$

Natürlich gibt es hier keinen Widerspruch, da jede Funktion, die mindestens einen linearen Raum verwendet, auch mindestens einen logarithmischen Raum verwendet. Das Schreiben von deutet jedoch darauf hin, dass eine Turing-Maschine möglicherweise weniger als linearen Speicherplatz benötigt. Warum sollten die Leute die ganze Zeit damit verbringen, beweisen, wenn dies genau dasselbe war? Was scheint eine triviale -Bindung zu sein? Was bedeutet es für eine Turing-Maschine, weniger als den linearen Raum zu verbrauchen?$\Omega(\log n)$$\Omega(\log n)$$\Omega(n)$

Bei beengten Platzverhältnissen verwenden wir das folgende Modell. Die Turing-Maschine verfügt über drei Bänder: ein schreibgeschütztes Eingabeband, ein schreibgeschütztes Arbeitsband und ein schreibgeschütztes Ausgabeband. Wir messen nur den Platzverbrauch auf dem Arbeitsband. Für Palindrome können wir mit Leerzeichen auf dem Arbeitsband FOR-Schleifen implementieren, die über die Eingabe gehen und übereinstimmende Zeichen an beiden Enden vergleichen. Jeder Index benötigt Speicherplatz zum Speichern.$O(\log n)$$O(\log n)$