<p>As you mention in <a href="https://cstheory.stackexchange.com/questions/979/automata-theory-formal-language-thesis-topic/986#986">Automata Theory / Formal Language Thesis Topic</a> my supervisors have at least some of the same intution about "reusable universality" as "better" than CA-style. Im not sure that a name is given though: <a href="http://www.diku.dk/~neil/blobentcs.pdf" rel="nofollow noreferrer">http://www.diku.dk/~neil/blobentcs.pdf</a></p>

<p>I havent focused much on that part, but as I see it, when going through biocomputing literature, the major difference lies in the meaning of the word "programming/programmable", e.g. what is it in fact that is programmable? That, and the "stored-program" part as well but I appreciate the nuance posed by your question</p>

<p>I've got no readily available answer to what it is called though</p>

CC BY-SA 2.5
2010-09-05T22:25:57.603Z
From their paper: "A program is software, not hardware.  Thus a program should itself be a concrete data object that can be replaced to specify different actions."  Thanks again.
Aaron Sterling
CC BY-SA 2.5
2010-10-06T19:51:02.827Z
I just stumbled on the work by Michael Conrad: http://portal.acm.org/citation.cfm?id=3533. He seems to be concered a bit by the same distinction that you are trying to make regarding "programmability" as the word he is using. Correct me if im wrong :)
svrist
CC BY-SA 2.5
2010-09-05T21:04:03.390Z
2010-09-05T21:04:03.390Z
2017-04-13T12:32:28.053Z
svrist
<p>There has been work in the PL/systems community on the semantics and modelling of operating systems.  As you point out, what you are talking about is much like an OS: it does something, but is guaranteed (well, in the case of an OS, guaranteed-ish) to return to a "ground state."  The PL people may not have formalized your notion of reusably universal, but you might find some inspiration there.</p>

<p>Your formalization will have to capture the difference between "a universal machine that, after it runs with one input, if you replace the input with another input it is ready to go" and "a universal machine that, given a sequence of input programs, runs them in succession."  And of course, all reasonable notions of universal machine probably satisfy the latter requirement.  So it seems quite tricky...</p>

CC BY-SA 2.5
2010-08-17T11:49:44.080Z
Thanks!  I don't have much programming language theory.  Time to learn some, I guess.
Aaron Sterling
CC BY-SA 2.5
2010-08-17T05:27:30.630Z
2010-08-17T05:27:30.630Z
Joshua Grochow
<p>There are several different (probably inequivalent) notions of computational universality (see for example the last couple pages of <a href="http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf">http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf</a>) and there is no consensus among experts about which notions are most correct (see for example <a href="http://cs.nyu.edu/pipermail/fom/2007-October/012148.html">http://cs.nyu.edu/pipermail/fom/2007-October/012148.html</a>).</p>

<p>I'm trying to say something about a particular model of biomolecular computation.  I'd like to argue that it's "more universal" or "more usefully universal" than some other models, because you can construct a universal machine that runs a program and then deletes the input at the end and is ready to run another program.  Contrast this to, say, cellular automata, which can emulate any Turing machine, but then at the end of the computation, you've got a final, unchangeable configuration.  To emulate another TM, you need to define a completely separate CA.  So I'd like to say something is "reusably universal" if it behaves like your desktop, not a CA (i.e., can execute multiple programs without needing to recreate the universe).  Has this notion been formalized anywhere?</p>

CC BY-SA 2.5
2010-08-17T14:47:36.383Z
You might change the question title to be a little less personal -- maybe just "Reusable universality?"
Joshua Grochow
<universal-computation>
Is there an official name for a notion of "reusably universal"?
Aaron Sterling
# Is there an official name for a notion of "reusably universal"?

(Asked by: username_0 on 2010-08-17)

There are several different (probably inequivalent) notions of computational universality (see for example the last couple pages of <http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf>) and there is no consensus among experts about which notions are most correct (see for example <http://cs.nyu.edu/pipermail/fom/2007-October/012148.html>).

I'm trying to say something about a particular model of biomolecular computation. I'd like to argue that it's "more universal" or "more usefully universal" than some other models, because you can construct a universal machine that runs a program and then deletes the input at the end and is ready to run another program. Contrast this to, say, cellular automata, which can emulate any Turing machine, but then at the end of the computation, you've got a final, unchangeable configuration. To emulate another TM, you need to define a completely separate CA. So I'd like to say something is "reusably universal" if it behaves like your desktop, not a CA (i.e., can execute multiple programs without needing to recreate the universe). Has this notion been formalized anywhere?

**Tags:** universal-computation
> **Comments:**
> **username_1**: You might change the question title to be a little less personal -- maybe just "Reusable universality?"  

---

## 2 answers

### Answer by username_2 on 2010-09-05. Score: 3 | Accepted answer

As you mention in [Automata Theory / Formal Language Thesis Topic](https://cstheory.stackexchange.com/questions/979/automata-theory-formal-language-thesis-topic/986#986) my supervisors have at least some of the same intution about "reusable universality" as "better" than CA-style. Im not sure that a name is given though: <http://www.diku.dk/~neil/blobentcs.pdf>

I havent focused much on that part, but as I see it, when going through biocomputing literature, the major difference lies in the meaning of the word "programming/programmable", e.g. what is it in fact that is programmable? That, and the "stored-program" part as well but I appreciate the nuance posed by your question

I've got no readily available answer to what it is called though

> **Comments:**
> **username_0**: From their paper: "A program is software, not hardware.  Thus a program should itself be a concrete data object that can be replaced to specify different actions."  Thanks again.  
> **username_2**: I just stumbled on the work by Michael Conrad: http://portal.acm.org/citation.cfm?id=3533. He seems to be concered a bit by the same distinction that you are trying to make regarding "programmability" as the word he is using. Correct me if im wrong :)  

---

### Answer by username_1 on 2010-08-17. Score: 4

There has been work in the PL/systems community on the semantics and modelling of operating systems. As you point out, what you are talking about is much like an OS: it does something, but is guaranteed (well, in the case of an OS, guaranteed-ish) to return to a "ground state." The PL people may not have formalized your notion of reusably universal, but you might find some inspiration there.

Your formalization will have to capture the difference between "a universal machine that, after it runs with one input, if you replace the input with another input it is ready to go" and "a universal machine that, given a sequence of input programs, runs them in succession." And of course, all reasonable notions of universal machine probably satisfy the latter requirement. So it seems quite tricky...

> **Comments:**
> **username_0**: Thanks!  I don't have much programming language theory.  Time to learn some, I guess.  

---

