Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite
1

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.

share|improve this question

1 Answer

up vote 3 down vote accepted

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's paper Expressiveness of Process Algebras 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 -- 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.

share|improve this answer
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 Jul 27 '11 at 14:03
I think it would be useful if you spelt out what you mean by 'implemented'. – Vijay D Jul 28 '11 at 10:15
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. – Martin Berger Jul 28 '11 at 11:17
@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 Jul 28 '11 at 14:37
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. – Martin Berger Jul 28 '11 at 15:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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