There are many universal computation systems. Turing machines, tag systems, rewrite systems, cellular automata to name just a few. The universality of a system is proved via reduction from a known universal (Turing-complete) model.

I am wondering if it is possible to define abstract conditions, that make each of the systems universal. For example, in definitions of algebraic structures, there are conditions (like: Closure, Associativity, etc.) that can be examined in a structure to determine if it is e.g. a group. There is no reduction from other structure, that is already known to be group.

Is it possible to define in similar way the universality? Are there any related works on the topic?

  • 1
    $\begingroup$ Your reduction in paragraph one is backwards; Turing-completeness of a model is proved via reduction from a known Turing-complete model. $\endgroup$ – Huck Bennett Feb 26 '12 at 4:55
  • 3
    $\begingroup$ Yes. The abstract condition is "It can simulate a Turing machine." I don't see how this is any less abstract than "It has an associative binary operation with a unique identity element, such that every element has an inverse." $\endgroup$ – Jeffε Feb 26 '12 at 11:11
  • $\begingroup$ Huck: thanks. Jeoe: more abstract, than "it can simulate a Turing machine" is IMO: "for any set of elements $A = \{ x : x=\{0,1\}^k \}$ and $B=\{ x : x = \{0,1\}^l \}$ it can implement function $f : A \rightarrow B$". What I want to say is that IMO the reduction approach is a practical tool rather than definition. $\endgroup$ – Mooncer Feb 26 '12 at 11:54
  • $\begingroup$ Universality is not defined as you have stated, as Jeff wrote it is defined solely based on the same model not by reduction to another model, e.g. there is a Turing machine $U$ that given $<M>,x$ where $M$ is a Turing machine, $U$ accepts iff $M$ accepts $x$. $\endgroup$ – Kaveh Feb 26 '12 at 19:40
  • 1
    $\begingroup$ I think you may want to clarify the question, since it seems to me that what you want: is a general condition that a given model is universal without talking about other models, and I think the definition itself satisfies what you want: there is a program in the model that has the sated property, i.e. there is a program $U$ in the model that given $<M>,x$ where $M$ is a program in the model, $U$ accepts iff $M$ accepts $x$. $\endgroup$ – Kaveh Feb 26 '12 at 19:44

Have a look at the work of Alex Heller and Robert di Paola on dominical categories. There should be further references there to older work.

| cite | improve this answer | |
  • $\begingroup$ I did not need to see this link two weeks before the ICFP deadline.... $\endgroup$ – Neel Krishnaswami Feb 26 '12 at 12:25
  • 2
    $\begingroup$ Let me know about your next deadline, I have a couple more in my sleeve. $\endgroup$ – Andrej Bauer Feb 26 '12 at 19:36

Your Answer

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

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