Hacker News new | ask | show | jobs
by honungsburk 509 days ago
I beleive you are wrong that "nobody has found a system of computation more powerful than Turing Machines". A turing machine can not perform indeterminacy, however, the actor model can.
3 comments

This is a misconception.

The actor model is a way to describe that a program exists, not if it’s possible to ‘compute’ that program.

You’re right that it can describe more things than a Turing machine, but doesn’t provide a constructive way to compute them.

Non-deterministic Turing machines [1] are the standard way to define Non-deterministic complexity classes like NP or NEXP, so there are definitely Turing machines with indeterminacy.

[1] https://en.wikipedia.org/wiki/Nondeterministic_Turing_machin...

I read that sentiment here a few years ago but couldn't get anything more out of it than actors can race, but a turing machine is determistic. I could very well have it wrong.

If you were computing with actors, and you also had a sufficiently-detailed spec about the actor model, is there some particular algorithm you could not compute by just executing a TLA+ spec of your actor algorithm using Turing-ish software?