Что означает сублинейное пространство для машин Тьюринга?

Доказано, что проблема определения, является ли вход палиндромом или нет, требует пространства на машине Тьюринга. Однако даже для сохранения входных данных требуется пространство  n , не значит ли это, что всем машинам Тьюринга требуется пространство Ω ( n ) ?$\Omega(\log n)$$n$$\Omega(n)$

Конечно, здесь нет противоречия, поскольку любая функция, которая использует хотя бы линейное пространство, также использует хотя бы логарифмическое пространство. Но написание действительно предполагает, что для машины Тьюринга возможно использовать меньше линейного пространства - в конце концов, зачем людям тратить все это время на доказательство Ω ( log n ), если это было в точности то же самое, что кажется тривиальная оценка Ω ( n ) ? Так что же означает, что машина Тьюринга использует меньше линейного пространства?$\Omega(\log n)$$\Omega(\log n)$$\Omega(n)$

$O(\log n)$$O(\log n)$