In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine.
In his paper "Actor Model of Computation: Scalable Robust Information Systems" Carl Hewitt proposes following hypothesis:
All physically possible computation can be directly implemented using Actors.
He comments that this hypothesis is an update to Church-Turing thesis that all physically computable functions can be implemented using the lambda calculus (or TM), stating that:
It is a consequence of the Actor Model that there are some computations that cannot be implemented in the lambda calculus.
Then he recalls Plotkin's informal proof of NTM to have property of bounded nondeterminism:
Now the set of initial segments of execution sequences of a given nondeterministic program P, starting from a given state, will form a tree. The branching points will correspond to the choice points in the program. Since there are always only finitely many alternatives at each choice point, the branching factor of the tree is always finite. That is, the tree is finitary. Now König's lemma says that if every branch of a finitary tree is finite, then so is the tree itself. In the present case this means that if every execution sequence of P terminates, then there are only finitely many execution sequences. So if an output set of P is infinite, it must contain a nonterminating computation.
Then he presents algorithm in Actor Model semantics which seem to have property of unbound nondeterminism, stating that the later proves the hypothesis above.
The algorithm is a computation of integer value. For NTM it is stated this way:
Step 1: Either print 1 on the next square of tape or execute Step 3.
Step 2: Execute Step 1.
Step 3: Halt
It's properties are: if NTM halts, there are only finite number of states which it can be in (bounded nonndeterminism, as shown by Plotkin); and it may never halt whatsoever (it has a subtree of computation of infinite depth).
For Actor Model it is stated like this:
- Create an Actor which can receive two messages: 'go' (makes it increment counter and send itself another 'go' message) and 'halt' (makes it return counter value).
- Send this actor 'go' and 'halt' messages.
Since Actor Model semantics state that a message is guaranteed to be delivered and there is no restriction on when will it be delivered, then if actor halts, there are infinite possible states in which it can be (unbounded nondeterminism); however, it will halt always.
However, it really doesn't seem to me to imply the hypothesis stated and it seems highly unlikely that we can actually achieve Actor Model semantics on a real hardware.
I'd like to propose following questions:
Does the property of unbounded nondeterminism really has to do something with computational power? Is 'computing an unbounded integer' algorithm really impossible to implement on any TM?
If so, what is the class of computations that requires it?
Edsger Dijkstra argued that is is impossible to implement system with unbounded nondeterminism; Tony Hoare agreed that the implementation should try to be reasonably fair. Is level of fairness achievable today is good enough to say that we can actually have computations which require this property implemented on physical hardware?
If we add an entropy source to NTM (or PTM) in form of fair random number generator, can we achieve the same unbounded nondeterminism property as in the Actor Model?