3
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 19:44

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I did not need to see this link two weeks before the ICFP deadline.... $\endgroup$
    – Neel Krishnaswami
    Feb 26, 2012 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, 2012 at 19:36

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.