Actor Model of Computation (2010) [pdf] | Hacker News Reader

Actor Model of Computation (2010) [pdf]

arxiv.org

117 pointsninjakeyboard31 comments

I find this resource confusing and annoying to read. When performing my thesis research I wasted a bunch of time trying to make sense of Hewitt's writing. I think a big problem is that the term "actor model" is so overloaded that it almost becomes meaningless. The actors that Hewitt is talking about is not at all the same as Erlang or Akka. As an example I consider this quote from the text nonsensical "Actor systems can perform computations that are impossible by Turing Machines" or of very little relevance to the actor models we use for programming. This has been discussed at [0].

For an overview of different actor models I prefer, see "43 years of actors: a taxonomy of actor models and their key properties" [1]. Agha's book [2] is also very good and I'd also like to recommend "Mixing Metaphors: Actors as Channels and Channels as Actors" [3].

[0]: http://lambda-the-ultimate.org/node/5208 [1]: http://soft.vub.ac.be/Publications/2016/vub-soft-tr-16-11.pd... [2]: https://dspace.mit.edu/handle/1721.1/6952 [3]: https://arxiv.org/abs/1611.06276

> "Actor systems can perform computations that are impossible by Turing Machines"

As a turing machine can compute anything that is computable it is therefore impossible for an Actor to do any computation that is not possible by a turing machine. This is computer science 101 and makes me wonder about the value of anything else said in the paper.

Well the interesting thing would be if that old lesson were violated.

Of course it's sealed forever for a specific definition of 'compute,' but I'm still open to the idea that we find something which resembles computation enough that we call it the same thing, yet its precise definition is different enough from the one used in connection with contemporary theory of computation that old proofs of universality won't necessarily apply to it.

That said... it seems unlikely to me that the Actor model does something non-trivially beyond what Turing machines are capable of, since it would likely be better known, and we would see Chomsky's hierarchy expanded to hold another class, etc. (Unless it goes beyond Turing Machines by being non-linguistic in some way, which could certainly be interesting. Maybe dealing with non-sequential symbols or something?)

Message passing was omitted from the Turing Model. (Two Turing Machines cannot send messages to each other.)

Message passing is fundamental for IoT, etc.

> it is therefore impossible for an Actor to do any computation that is not possible by a turing machine

It is impossible for Actors implemented on a Turing machine to do anything that a Turing machine cannot. But the Actor model itself is larger than a Turing machine - eg nondeterminism.

Turing completeness is a lower bound on computation, not a maximum. For instance, a CPU with a hardware random number generator is a Turing machine, but a (basic/strict/pure) Turing machine cannot emulate a CPU with a hardware random number generator!

Probably, the most fundamental misunderstanding of the Actor Model is that it is based on "Event Loops" which require the following: When an Actor receives a message, it must run until it produces a response to the message and then loops back to receive another message. However, a ReadersWriter scheduler must be able to receive more read and write messages even while it is still processing a message as explained in https://www.amazon.com/Inconsistency-Robustness-Studies-Logi... Even so, a ReadersWriter scheduler must obey the Mutual Exclusion Principle, which says that only one activity can execute in an Actor at a time.

Another common misunderstanding is that an an Actor must have a mailbox, message queue, or event queue. There would be an infinite regress if any of these were required because since everything is an Actor, each of these would itself need a mailbox, message queue, or event queue!

Only that Carl took part in research into the model a few decades ago [1] when there was no Erlang, according to wikipedia.

[1] Carl Hewitt; Peter Bishop & Richard Steiger (1973). "A Universal Modular Actor Formalism for Artificial Intelligence". IJCAI.

Turing machines are not very good handling uncertainty? the key pond is on physics ? yada, yada? I thought this was 101 already!

For a more recent description of the Actor Model and associated work, see the following: https://www.amazon.com/Inconsistency-Robustness-Studies-Logi...

Also, those who will be in London on November 9 can come to my Code Mesh Keynote. See https://plus.google.com/+CarlHewitt-StandardIoT/posts/BXSZ7Y...

It is fair to say that the implementation of Actors is still in its infancy. There is a startup in Silicon Valley that is attempting to remedy this situation. They are looking for expert programming language and run-time implementers ;-)

Older publications are obsolete and unfortunately many of them have errors (including my own!). I wrote the Wikipedia article on the Actor Model but am no longer allowed to update it :-(

Actors are very well defined up to a unique isomorphism by axioms.

The reason that Actors can perform computations that Turing Machines cannot is that the Turing Machine model left out message passing.

> "Older publications are obsolete and unfortunately many of them have errors (including my own!). I wrote the Wikipedia article on the Actor Model but am no longer allowed to update it :-("

As someone who's been interested in the Actor Model recently, thanks for this statement, and the link to the book you've provided.

This would help avoid going down the wrong path.

Thanks!

Additional information that you might find helpful is here: https://plus.google.com/+CarlHewitt-StandardIoT

Awesome overview! I've built actor -oriented implementations in a variety of domains, from finance to education to messaging, and find it a very useful way to think about the world. It can focus your thinking around which state (and actions) should be colocated, and orient you towards event based interfaces that focus around that data rather than specific client needs. People coming from modern programming paradigms will find many useful analogies -- e.g. to SOA/microservice decomposition, to components in a redux event loop.

Some cautions: as with any factorization scheme, granularity is important. The actor model makes it easy to think within actors, and hard to reason about interactions. Don't overfactor!

Also, orienting around event streams means forgoing synchronous requests. This can lead to insane complexity where each actor awaits specific replies to act on remote state. When adopting a framework, never ignore the useful tools it leaves behind (like the way synchronous request interfaces imply a round trip handshake being handled by another layer).

Carl Hewitt, Erik Meijer, Clemens Szyperski, talking about the actor model in 2012.

https://www.youtube.com/watch?v=1zVdhDx7Tbs

Hewitt is now kind of a crank. When Hofstadter came over for the Symsys thing in Stanford a few years back, Hewitt handed Hofstadter a little sheet of paper saying that mere contradiction allowed axiomatic systems to transcend Godel incompleteness theorems. Hofstadter: "Thanks, Carl." and then he threw it away when Hewitt wasn't looking. I think there's a thread in Lambda the Ultimate.

Unfortunately, it is very common to have difficulty with paradigm shifts :-(

Those of you near Denver can come to my BLAST 2018 lecture at 5PM on August 9 at the University of Denver with the following abstract: https://plus.google.com/+CarlHewitt-StandardIoT/posts/hh5CYE...

You really don't understand computability at all, do you?

Please don't make personal attacks—just post civilly and substantively.

https://news.ycombinator.com/newsguidelines.html

That's not a personal attack, it's an honest question.

SCTB is correct.

Sticking to the subject matter is the way to go.

IMODE: Which part of the Actor Model theory of computation do you not understand?

You can see a flash of that in this article with "Actor systems can perform computations that are impossible by Turing Machines"

The statement is true, Actor systems can handle uncertainty in ways that Turing Machines can not.

Actor systems are no more able to handle uncertainty than Turing Machines are, either via nondeterministic TMs or by deterministic TMs. This is basic computability theory.

That is wrong, Actor systems have a property called "Unbounded nondeterminism" nondeterministic TM have only bounded nondeterminism.

https://en.wikipedia.org/wiki/Unbounded_nondeterminism

Jean is correct!

Of course, unbounded nondeterminism is a somewhat artificial example. However, the extra power of Actors over Turing Machines is critical for IoT and the implementation of Intelligent Systems.

I'm sorry, but unless you produce a proof of hypercomputation with models that have unbounded determinism, you're a crank.

As explained in the articles referenced, Actor systems have unbounded nondeterminism because of indeterminacy.

No "hypercomputation" is required ;-)

and yet it moves

Hewitt work so relevant today, I found interesting that the Lisp Scheme was a failed attempt to implement this model of computation, ORGs, the scientific community metaphor, Planner, Inconsistency robustness, he even have a paper with David Marr from the same year of Actors "Video Ergo Scio" related today with the idea of inverse 3D graphics of capsules.

According to the abstract at https://arxiv.org/abs/1008.1459 , this document has been revised many times (the current version, from 2015, is v38). Is there a particular reason that v8 was the version selected for submission?

I created a library for multiprocessing, which is loosely based on actor model.

The interesting bit is that you'll never have to do the wiring yourself, zproc does it all in the background.

https://github.com/pycampers/zproc

I prefer the rapper actor model astronaut form of compuation, but hey, CSP and STM are cool too. Sorry, couldn’t help it. And RDMA is, and always will be, pure evil.

Reply on news.ycombinator.com