10
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You might change the question title to be a little less personal -- maybe just "Reusable universality?" $\endgroup$
    – Joshua Grochow
    Aug 17, 2010 at 14:47

2 Answers 2

Reset to default
3
$\begingroup$

As you mention in Automata Theory / Formal Language Thesis Topic 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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aaron Sterling
    Sep 5, 2010 at 22:25
  • $\begingroup$ I just stumbled on the work by Michael Conrad: 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 :) $\endgroup$
    – svrist
    Oct 6, 2010 at 19:51
4
$\begingroup$

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...

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! I don't have much programming language theory. Time to learn some, I guess. $\endgroup$
    – Aaron Sterling
    Aug 17, 2010 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.