Re:Actor Model of Computation (2010) [pdf]
by mindslight on Thursday August 02, 2018 @01:58PM
(#17673757)
> 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!
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!