Apa arti ruang sublinear untuk mesin Turing?

Masalah memutuskan apakah input adalah palindrom atau tidak telah terbukti membutuhkan ruang pada mesin Turing. Namun, bahkan menyimpan input membutuhkan ruang  jadi bukankah itu berarti bahwa semua mesin Turing memerlukan ruang ?$\Omega(\log n)$$n$$\Omega(n)$

Tentu saja, tidak ada kontradiksi di sini, karena fungsi apa pun yang menggunakan setidaknya ruang linear juga menggunakan setidaknya ruang logaritmik. Tetapi menulis menunjukkan bahwa mesin Turing mungkin menggunakan kurang dari ruang linier - setelah semua, mengapa orang menghabiskan seluruh waktu untuk membuktikan jika itu adalah hal yang persis sama apa yang kelihatannya terikat sepele ? Jadi apa artinya bagi mesin Turing untuk menggunakan kurang dari ruang linear?$\Omega(\log n)$$\Omega(\log n)$$\Omega(n)$

Saat berhadapan dengan ruang terbatas, kami menggunakan model berikut. Mesin Turing memiliki tiga kaset: tape input read-only, tape work read-write, dan tape output read-only. Kami hanya mengukur konsumsi ruang pada pita kerja. Untuk palindrom, dengan spasi pada work tape kita bisa menerapkan loop UNTUK yang melewati input, membandingkan karakter yang cocok di kedua ujungnya. Setiap indeks membutuhkan ruang untuk menyimpan.$O(\log n)$$O(\log n)$