9
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jun 10, 2012 at 11:24
  • $\begingroup$ @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. $\endgroup$
    – Adi Shavit
    Commented Jun 10, 2012 at 11:40
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jun 10, 2012 at 11:47
  • 1
    $\begingroup$ Googling around I found a recent paper with nice results about Turing completeness and decidability of Actor Systems: Decidability Problems for Actor Systems $\endgroup$
    – Vor
    Commented Sep 5, 2012 at 21:13
  • 1
    $\begingroup$ 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). $\endgroup$
    – paulotorrens
    Commented Sep 15, 2017 at 14:32

1 Answer 1

Reset to default
-3
$\begingroup$

computer scientists generally are of the consensus that the Church Turing thesis[1] is correct and definitive, ie that Turing machines describe computation, and that more powerful forms do not really exist, and take assertions that some model is "more powerful" than Turing machines with extreme skepticism, even near hostility.[2] neophytes to the field who dont fully understand the concept are prey to near-marketing slogans of some theory as "more powerful" than Turing machines but those claims are rarely made by mainstream/reputable computer scientists.

but as a flip side to this, many models of computation are Turing complete. therefore in CS there is in practice mostly a tolerant, "live and let live" attitude with many different models of computation proliferating depending on what is most relevant and convenient for the problem studied. most basic programming models are Turing complete with basic structures such as memory, conditionals, and loops, subroutines etcetera. so more reasonable claims are, "model [x] is better suited to study [y] because [z]". the Actor model focuses on message passing, communication, concurrency & some security.

nevertheless there is some mostly philosophical debate in CS about some models being "more powerful".

[1] Church Turing thesis

[2] Interactive models of computing vs Church Turing thesis

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ As I said, Actors are NOT more powerful in what they can compute. They are (claimed to be) more powerful by featuring "unbounded nondeterminism" which is related to concurrent operation. What you are referring to is hypercomputation, which is not the subject of my question. $\endgroup$
    – Adi Shavit
    Commented Sep 6, 2012 at 5:37
  • $\begingroup$ ?! huh! bummer! didnt see anything about unbounded nondeterminism in your actual question above. also made no direct ref to hypercomputation in my answer. which is indeed one area of study of non-Turing completeness, but the ref I gave is another involving "interactive models" $\endgroup$
    – vzn
    Commented Sep 6, 2012 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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