# Turing Machine-Like Formalism for The Actor Model

Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.

The Actor Model is sometimes mentioned as a more powerful computational-model than Turing machines (not in what it can compute, but in other aspects).

1. Is The Actor Model a full fledged Turning machine alternative as a computational model?
2. Does The Actor Model also have such a symbol-based formal computation description akin to the Turing machine?
3. Are the actors assumed to be Turing machine equivalent - since each message is processed sequentially (and atomically)?

There are many theoretical results based on Turing machines, e.g. the halting problem, decidability, relation to Gödel's incompleteness theorem etc.

Can these proofs be formally generalize to the Actor Model? Has this been done?

• I think actors (as in Erlang) are usually assumed to be Turing complete. There is, however, vast research about all kinds of cooperating automata. There are also process calculi. I think the question is broader than you anticipated. Maybe you should focus the question by providing a specific example of a system you want to have formal models for, so people can see what you are after. – Raphael Jun 10 '12 at 11:24
• @Raphael: Do you happen to have a reference that actors in the Actor Model are assumed to be Turing complete? I am interested in the fundamentals of computation with such models. – Adi Shavit Jun 10 '12 at 11:40
• It really depends where you take the term "actor model" from. I know it from Erlang and libraries for other languages that mimick Erlang, and those have no restrictions on the power of a single actor (hence they are, in the theory world, Turing-complete). By the way, the Wikipedia article you link provides tons of references; have you checked those? See also this one. – Raphael Jun 10 '12 at 11:47
• Googling around I found a recent paper with nice results about Turing completeness and decidability of Actor Systems: Decidability Problems for Actor Systems – Vor Sep 5 '12 at 21:13
• The pi calculus comes to mind, which is a proces calculi as state by @Raphael above. It is a model of computation (Turing-complete, as it can encode the lambda calculus). All models of computation are equivalent face the same problems (as in: none of them can solve the halting problem, etc). – paulotorrens Sep 15 '17 at 14:32