<p>Have a look at the work of Alex Heller and Robert di Paola on <a href="http://www.jstor.org/pss/2274352" rel="nofollow">dominical categories</a>. There should be further references there to older work.</p>

CC BY-SA 3.0
2012-02-26T12:25:31.687Z
I did not need to see this link two weeks before the ICFP deadline....
Neel Krishnaswami
CC BY-SA 3.0
2012-02-26T19:36:01.620Z
Let me know about your next deadline, I have a couple more in my sleeve.
Andrej Bauer
CC BY-SA 3.0
2012-02-26T09:34:50.827Z
2012-02-26T09:34:50.827Z
Andrej Bauer
<p>There are many universal computation systems. <strong>Turing machines, tag systems, rewrite systems, cellular automata</strong> to name just a few. The universality of a system is proved via reduction from a known universal (Turing-complete) model.</p>

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

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

CC BY-SA 3.0
2012-02-26T04:55:45.837Z
Your reduction in paragraph one is backwards; Turing-completeness of a model is proved via reduction from a known Turing-complete model.
Huck Bennett
CC BY-SA 3.0
2012-02-26T11:11:36.517Z
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."
Jeffε
CC BY-SA 3.0
2012-02-26T11:54:41.727Z
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.
Mooncer
CC BY-SA 3.0
2012-02-26T19:40:02.473Z
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$.
Kaveh
CC BY-SA 3.0
2012-02-26T19:44:46.740Z
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$.
Kaveh
CC BY-SA 3.0
2012-02-26T22:48:53.577Z
Kaveh I have hard time understanding your definition. Is the statement that I wrote – that universality allows to implement arbitrary function – really incorrect?
Mooncer
CC BY-SA 3.0
2012-02-27T14:28:15.677Z
Yes, really incorrect.  There are uncountably many boolean functions over the set of finite bit strings, but there are only countably many Turing machines, tag systems, rewrite systems, cellular automata, Gödel numbers, et cetera, ad nauseam.
Jeffε
<computability><turing-machines><universal-computation>
Abstract definition of universal computation
Mooncer
# Abstract definition of universal computation

(Asked by: username_0 on 2012-02-26)

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?

**Tags:** computability, turing-machines, universal-computation
> **Comments:**
> **username_1**: Your reduction in paragraph one is backwards; Turing-completeness of a model is proved via reduction from a known Turing-complete model.  
> **username_2**: 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."  
> **username_0**: 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.  
> **username_3**: 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$.  
> **username_3**: 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$.  
> **username_0**: Kaveh I have hard time understanding your definition. Is the statement that I wrote – that universality allows to implement arbitrary function – really incorrect?  
> **username_2**: Yes, really incorrect.  There are uncountably many boolean functions over the set of finite bit strings, but there are only countably many Turing machines, tag systems, rewrite systems, cellular automata, Gödel numbers, et cetera, ad nauseam.  

---

## 1 answers

### Answer by username_4 on 2012-02-26. Score: 4

Have a look at the work of Alex Heller and Robert di Paola on [dominical categories](http://www.jstor.org/pss/2274352). There should be further references there to older work.

> **Comments:**
> **username_5**: I did not need to see this link two weeks before the ICFP deadline....  
> **username_4**: Let me know about your next deadline, I have a couple more in my sleeve.  

---

