<p>I have heard it said that time is more precious than space because we can reuse space but not time.  What if we treat space with this much reverence?</p>

<h3>What is generally known about models of computation in which space is immutable?</h3>

<p>I would expect such models to initialize each memory cell to some "blank" state and then only allow the writing of some "non-blank" value to each cell at most once.</p>

<p>The study of <a href="https://en.wikipedia.org/wiki/Persistent_data_structure" rel="noreferrer">persistent data structures</a> seems to me like a possible way to answer this question.</p>

<p>I thought of this question while studying functional programming, which highly values immutability.</p>

CC BY-SA 4.0
2019-01-06T20:55:16.100Z
https://cs.stackexchange.com/questions/18939/relation-between-space-and-time-complexity-for-machines-with-write-once-read-man
Thomas Klimpel
CC BY-SA 4.0
2019-01-06T20:56:53.260Z
https://en.wikipedia.org/wiki/Wang_B-machine
Thomas Klimpel
CC BY-SA 4.0
2019-01-06T23:30:40.433Z
A TM with one infinite tape in which each blank cell can only be written once can simulate a standard Turing machine. Just keep a placeholder of the head in the tape: $\# b x_1 b x_2 b ... b x_n b H b y_1 b y_2 b ... b y_n  b \#$. The Turing machine at each step scans the whole tape, reads three symbols at once and make a (reversed) copy of the current content of the tape on the right: $\#x_1 * x_2 *... x_n * H * y_1 * y_2 * ... * y_n * \# b y_n b ... b y_2 b z b x_n b H b x_{n-1} b ... b x_2 b x_1 b\#$ ($y_1$ replaced by $z$ and head moves left, $*$ replaces the blank $b$ during the copy)
Marzio De Biasi
<reference-request><ds.data-structures><functional-programming><space-complexity>
Immutable Space Model
Tyson Williams
# Immutable Space Model

(Asked by: username_0 on 2019-01-06)

I have heard it said that time is more precious than space because we can reuse space but not time. What if we treat space with this much reverence?

### What is generally known about models of computation in which space is immutable?

I would expect such models to initialize each memory cell to some "blank" state and then only allow the writing of some "non-blank" value to each cell at most once.

The study of [persistent data structures](https://en.wikipedia.org/wiki/Persistent_data_structure) seems to me like a possible way to answer this question.

I thought of this question while studying functional programming, which highly values immutability.

**Tags:** reference-request, ds.data-structures, functional-programming, space-complexity

> **Comments:**
> **username_1**: https://cs.stackexchange.com/questions/18939/relation-between-space-and-time-complexity-for-machines-with-write-once-read-man  
> **username_1**: https://en.wikipedia.org/wiki/Wang_B-machine  
> **username_2**: A TM with one infinite tape in which each blank cell can only be written once can simulate a standard Turing machine. Just keep a placeholder of the head in the tape: $\# b x_1 b x_2 b ... b x_n b H b y_1 b y_2 b ... b y_n  b \#$. The Turing machine at each step scans the whole tape, reads three symbols at once and make a (reversed) copy of the current content of the tape on the right: $\#x_1 * x_2 *... x_n * H * y_1 * y_2 * ... * y_n * \# b y_n b ... b y_2 b z b x_n b H b x_{n-1} b ... b x_2 b x_1 b\#$ ($y_1$ replaced by $z$ and head moves left, $*$ replaces the blank $b$ during the copy)  

---

## 0 answers

