<p>This question is too vague to admit a clearcut answer, but it points towards a fascinating research field. The key problem is that neither is the actor model formally well-defined, nor is the notion of equivalency between (formalised) models of computation clear. Defining what expressivity of programming languages means precisely is a wide open problem, particularly for models of concurrent computation. It's unlikely that there is one clearcut notion of expressivity. Instead, language expressivity would appear to be parametric in properties of interest. <a href="http://user.it.uu.se/~joachim/" rel="noreferrer">Joachim Parrow</a>'s paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.7752&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Expressiveness of Process Algebras</a> gives an overview of the problem area, and explains some approaches that have been used to tackle it. There's even an annual conference -- <a href="http://www.lix.polytechnique.fr/comete/EXPRESS11/" rel="noreferrer">Express</a> -- dedicated to this question.</p>

<p>Process calculi such as CCS, CSP or &pi;-calculi were developed in parts to offer a formalisation of actors, but are themselves of varying expressivity w.r.t. various elaborations of the latter concept. Even seemingly small variations in the operations a process calculus offers leads to huge expressivity gaps w.r.t.  various notions of expressivity.</p>

CC BY-SA 3.0
2011-07-27T14:03:13.277Z
Specifically what I'm looking for is **can one be implemented in the other**? And if so, is there a paper with the proof? (I'm not concerned with *expressiveness* because of the inexact meaning of that.)
chrisaycock
CC BY-SA 3.0
2011-07-28T10:15:20.977Z
I think it would be useful if you spelt out what you mean by 'implemented'.
Vijay D
CC BY-SA 3.0
2011-07-28T11:17:47.427Z
Chris, the 'curse' of the Church-Turing thesis means that you can implement actors as cellular automata, or in Fortran. The study of expressivity starts with the realisation that implementability according to the Church-Turing thesis is too coarse a criterion for equivalency of programming languages. Theoretical musings aside, I suggest that the asynchronous pi-calculus is a good starting point if you are interested in formal models of actors.
Martin Berger
CC BY-SA 3.0
2011-07-28T14:37:28.940Z
@Martin I think I see what you mean. From Parrow's paper, since there are numerous ways to interpret *semantic preservation*, so as long as a transition system is Turing-complete, we've pretty much hit the end of our investigation of equivalence. Am I getting that right?
chrisaycock
CC BY-SA 3.0
2011-07-28T15:13:15.283Z
I'd stay it's the other way round: as programmers we know
that some kinds software is more easily written and
maintained in some languages than others (e.g. garbage collected
vs manual memory management, message-passing vs
shared memory), as language implementors, we know that some
features are more easily implemented than others (e.g. resumable
vs 'normal' exceptions, or asynchronous vs synchronous message
passing, or atomic broadcast in distributed systems). The study
of expressivity seeks to work out in detail what makes a language
feature expressive, and what makes it hard to implement.
Martin Berger
CC BY-SA 3.0
2011-07-27T09:57:48.077Z
2011-07-27T10:38:35.973Z
2011-07-27T10:38:35.973Z
Martin Berger
<p>I often see casual mention that the Hewit/Agha Actor Model is equivalent in capability to process algebra, like CSP, CCS and ACP. Ie, <strong>one can be implemented in the other</strong>. Is there a paper that actually contains the proof of this? I'm specifically looking for a citable reference.</p>

<reference-request><concurrency><process-algebra>
Are the Actor Model and Process Algebra "equivalent"?
chrisaycock
# Are the Actor Model and Process Algebra "equivalent"?

(Asked by: username_0 on 2011-07-26)

I often see casual mention that the Hewit/Agha Actor Model is equivalent in capability to process algebra, like CSP, CCS and ACP. Ie, **one can be implemented in the other**. Is there a paper that actually contains the proof of this? I'm specifically looking for a citable reference.

**Tags:** reference-request, concurrency, process-algebra

---

## 1 answers

### Answer by username_1 on 2011-07-27. Score: 5 | Accepted answer

This question is too vague to admit a clearcut answer, but it points towards a fascinating research field. The key problem is that neither is the actor model formally well-defined, nor is the notion of equivalency between (formalised) models of computation clear. Defining what expressivity of programming languages means precisely is a wide open problem, particularly for models of concurrent computation. It's unlikely that there is one clearcut notion of expressivity. Instead, language expressivity would appear to be parametric in properties of interest. [Joachim Parrow](http://user.it.uu.se/~joachim/)'s paper [Expressiveness of Process Algebras](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.7752&rep=rep1&type=pdf) gives an overview of the problem area, and explains some approaches that have been used to tackle it. There's even an annual conference -- [Express](http://www.lix.polytechnique.fr/comete/EXPRESS11/) -- dedicated to this question.

Process calculi such as CCS, CSP or π-calculi were developed in parts to offer a formalisation of actors, but are themselves of varying expressivity w.r.t. various elaborations of the latter concept. Even seemingly small variations in the operations a process calculus offers leads to huge expressivity gaps w.r.t. various notions of expressivity.

> **Comments:**
> **username_0**: Specifically what I'm looking for is **can one be implemented in the other**? And if so, is there a paper with the proof? (I'm not concerned with *expressiveness* because of the inexact meaning of that.)  
> **username_2**: I think it would be useful if you spelt out what you mean by 'implemented'.  
> **username_1**: Chris, the 'curse' of the Church-Turing thesis means that you can implement actors as cellular automata, or in Fortran. The study of expressivity starts with the realisation that implementability according to the Church-Turing thesis is too coarse a criterion for equivalency of programming languages. Theoretical musings aside, I suggest that the asynchronous pi-calculus is a good starting point if you are interested in formal models of actors.  
> **username_0**: @Martin I think I see what you mean. From Parrow's paper, since there are numerous ways to interpret *semantic preservation*, so as long as a transition system is Turing-complete, we've pretty much hit the end of our investigation of equivalence. Am I getting that right?  
> **username_1**: I'd stay it's the other way round: as programmers we know that some kinds software is more easily written and maintained in some languages than others (e.g. garbage collected vs manual memory management, message-passing vs shared memory), as language implementors, we know that some features are more easily implemented than others (e.g. resumable vs 'normal' exceptions, or asynchronous vs synchronous message passing, or atomic broadcast in distributed systems). The study of expressivity seeks to work out in detail what makes a language feature expressive, and what makes it hard to implement.  

---

