# Abstract definition of universal computation

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?

• Your reduction in paragraph one is backwards; Turing-completeness of a model is proved via reduction from a known Turing-complete model. Feb 26, 2012 at 4:55
• 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." Feb 26, 2012 at 11:11
• 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. Feb 26, 2012 at 11:54
• 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$. Feb 26, 2012 at 19:40
• 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$. Feb 26, 2012 at 19:44