Penggunaan terukur oleh Savitch

Dalam makalah Savitch 1969, "Hubungan Antara Nondeterministik dan Kompleksitas Pita Deterministik", ia menyatakan bahwa "semua fungsi penyimpanan umum L (n)> = lg n dapat diukur. Khususnya, setiap polinomial dalam n dan lg n dapat diukur." Definisinya yang dapat diukur adalah: "Suatu fungsi L (n) dikatakan dapat diukur jika ada beberapa mesin Turing dengan hanya satu pita penyimpanan sehingga, dengan input panjang apa pun n, mesin akan berhenti setelah perhitungan di mana penyimpanan tersebut kepala kaset memindai tepat kotak L (n). "

Jadi, masalah saya adalah, berdasarkan definisinya, saya tidak mengerti mengapa fungsi penyimpanan L (n)> = lg n dapat diukur, sedangkan fungsi L (n) <lg n tidak akan. Apakah ini entah bagaimana tersirat dalam definisinya? Atau ada beberapa publikasi yang harus saya baca?

Saya pikir definisi ini sekarang dikenal dengan istilah fungsi ruang-konstruksi . Ada fungsi dalam ruang sublogarithmic yang membangun ruang, sementara yang lain tidak.

http://dl2.acm.org/citation.cfm?id=31171 Andrzej Szepietowski: Tidak ada fungsi konstruktif ruang penuh antara log log n dan log n. Pemrosesan Informasi Surat 24 (6), 361-362.