@Article{RS82c, author = { Ronald L. Rivest and Adi Shamir }, title = { How to reuse a ``write-once'' memory }, journal = { Information and Control }, issn = { 0019-9958 }, OPTyear = { 1982 }, date = { 1982-10 }, issue = { October-December }, volume = { 55 }, number = { 1--3 }, pages = { 1--19 }, doi = { 10.1016/S0019-9958(82)90344-8 }, url = { http://www.sciencedirect.com/science/article/pii/S0019995882903448 }, publisher = { Academic Press }, abstract = { Storage media such as digital optical disks, {PROMS}, or paper tape consist of a number of ``write-once'' bit positions (\emph{wits}); each wit initially contains a ``0'' that may later be \emph{irreversibly} overwritten with a ``1.'' It is demonstrated that such ``write-once memories (\emph{woms}) can be ``rewritten'' to a surprising degree. For eacmple, only 3 wits suffice to represent any 2-bit value in a way that can later be updated to represent any other 2-bit value. For large $k$, $1.29\ldots\cdot k$ wits suffice to represent a $k$-bit value in a way that can be similarly updated. Most surprising, allowing $t$ writes of a $k$-bit value requires only $t+o(t)$ wits, for any fixed $k$. For fixed $t$, approximately $k\cdot t/\log(t)$ wits are required as $k\rightarrow \infty$. An $n$-wite {WOM} is shown to have a ``capacity'' (i.e., $k\cdot t$ when writing a $k$-bit value $t$ times) of up to $n\cdot\log(n)$ bits. }, }