<p>I think that this definition is nowadays known under the term <a href="http://en.wikipedia.org/wiki/Space-constructible_function%20space-constructible%20function">space-constructible function</a>. There are functions in sublogarithmic space that are space constructible, while others are not. </p>

<p><a href="http://dl2.acm.org/citation.cfm?id=31171">http://dl2.acm.org/citation.cfm?id=31171</a> Andrzej Szepietowski: There are no fully space constructible functions between log log n and log n. Information Processing Letters 24(6),361-362.</p>

CC BY-SA 3.0
2012-10-14T19:10:55.083Z
Great!  I'll give that paper a read.  Thank you, Hermann.
djkern
CC BY-SA 3.0
2012-10-14T16:26:52.370Z
2012-10-14T16:26:52.370Z
Hermann Gruber
<p>In Savitch's 1969 paper, "Relationships Between Nondeterministic and Deterministic Tape Complexities", he states that "all common storage functions L(n) >= lg n are measurable. In particular, any polynomial in n and lg n is measurable."  His definition of measurable is:  "A function L(n) is said to be measurable if there is some Turing machine with just one storage tape such that, given any input of length n, the machine will halt after a computation in which the storage tape head scans exactly L(n) squares." </p>

<p>So, my problem is, based on his definition, I don't understand why storage functions L(n) >= lg n would be measurable, while functions L(n) &lt; lg n would not be.  Is this somehow implicit in his definition?  Or are there some publications that I should read?</p>

<cc.complexity-theory><pspace><space-complexity>
Savitch's use of measurability
djkern
# Savitch's use of measurability

(Asked by: username_0 on 2012-10-14)

In Savitch's 1969 paper, "Relationships Between Nondeterministic and Deterministic Tape Complexities", he states that "all common storage functions L(n) >= lg n are measurable. In particular, any polynomial in n and lg n is measurable." His definition of measurable is: "A function L(n) is said to be measurable if there is some Turing machine with just one storage tape such that, given any input of length n, the machine will halt after a computation in which the storage tape head scans exactly L(n) squares."

So, my problem is, based on his definition, I don't understand why storage functions L(n) >= lg n would be measurable, while functions L(n) < lg n would not be. Is this somehow implicit in his definition? Or are there some publications that I should read?

**Tags:** cc.complexity-theory, pspace, space-complexity


---

## 1 answers

### Answer by username_1 on 2012-10-14. Score: 9 | Accepted answer

I think that this definition is nowadays known under the term [space-constructible function](http://en.wikipedia.org/wiki/Space-constructible_function%20space-constructible%20function). There are functions in sublogarithmic space that are space constructible, while others are not.

<http://dl2.acm.org/citation.cfm?id=31171> Andrzej Szepietowski: There are no fully space constructible functions between log log n and log n. Information Processing Letters 24(6),361-362.

> **Comments:**
> **username_0**: Great!  I'll give that paper a read.  Thank you, Hermann.  

---

