6
$\begingroup$

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 seems to me like a possible way to answer this question.

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ cs.stackexchange.com/questions/18939/… $\endgroup$ – Thomas Klimpel Jan 6 '19 at 20:55
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Wang_B-machine $\endgroup$ – Thomas Klimpel Jan 6 '19 at 20:56
  • 2
    $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Jan 6 '19 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.