Hacker News new | past | comments | ask | show | jobs | submit login

> "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!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: