What Turing and Church Left Out

Concurrent message passing was crucially omitted from the lambda calculus [Church 1932], Turing Machines (TM) [Turing 1936], Simula-67 [Dahl and Nygaard 1967], and Logic Programs [Hewitt 1969], thereby crippling them as a foundation for the Internet of Things (IoT). Actors [Hewitt, et. al 1973] remedied the omission to provide for scalable computation. An Actor message passing machine can be millions of times faster than any corresponding pure Logic Program or parallel nondeterministic lambda expression. Since the time of this early work, message passing has grown to be one of the most important paradigms in computing [Hewitt and Woods 2018; Hoare 2016; Milner 1993].

Of course, earlier work made huge pioneering contributions: lambda expressions play an important role in programming languages. TM inspired development of the stored program sequential computer. Simula-67 became the basis for object-oriented programming in Java and C++. Logic Programs are fundamental to Scalable Intelligent Systems. [Hewitt and Woods 2018]

Message Passing in Practice

Concurrency control for readers and writers in a database is a classic problem that illustrates the power of message passing. The fundamental constraint is that multiple writers are not allowed to operate concurrently in the database and a writer is not allowed to operate concurrently with a reader. In the figure below for an Actor machine

• Yellow is used for the Actor’s region of mutual exclusion
• Within the region of mutual exclusion, a hole in grey allows other messages to be processed which are of two kinds:
  1. Queue (shown as rectangle) hole in which the current activity can be suspended until resumed
  2. Call-out (shown as oval) hole for a request made outside the region of mutual exclusion

Many different policies could be implemented in the above scheduler including the following:

•  Reader priority: When a writer comes out of the database, resume all in ReadersQ.
•  Writer priority: When a writer comes out of the database and both WritersQ and ReadersQ are nonempty, resume just one in ReadersQ, and then when it comes of the database resume one in WritersQ.

Computation that cannot be done by lambda Calculus, TM, or pure Logic Programs

Actor message passing machines can perform computations that a no lambda expression, nondeterministic Turing Machine, Simula-67 program, or pure Logic Program can implement. Below is an example of a very simple computation that cannot be performed by a nondeterministic TM:

There is an always-halting Actor message passing machine that can compute an integer of unbounded size. This is accomplished using variables count initially 0 and continue initially True. The computation is begun by concurrently sending over the Internet two messages to the Actor machine: a stop request that will return an integer n formalized as Output[n] and a go message that will return Void.

  The Actor machine operates as follows:

• When a go message is received:
  • If continue is True, increment count by 1, send this Actor machine a go message in a hole of the region of mutual exclusion, and afterward return Void.
  •  If continue is False, return Void.
• When a stop message is received, return count and set continue to False for the next message received.

Theorem. There is no lambda expression, nondeterministic Turing Machine, Simula-67 program, or pure Logic Program that implements the above computation.

    Proof [Plotkin 1976]:

“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.”

 

Limitations of 1^st Order Logic for Concurrent Computation

Theorem. It is well known that there is no 1^st order theory for the above Actor machine.

Proof. Every 1^st order theory is compact meaning that every inconsistent set of propositions has a finite inconsistent subset. Consequently, to show that there is no 1^st order theory, it is sufficient to show that there is an inconsistent set of propositions such that every finite subset is consistent. The set of propositions NoOutput defined to be {~Output[i] | i:N} is inconsistent meaning |-~NoOutput (because ⊢∃[i:N] Output[i], i.e., the Actor machine always outputs an integer) but every finite subset S of NoOutput is consistent meaning ~|-~S (because by finiteness of S, there is an upper bound b:N such that S is a subset of {~Output[i] | i<b} but ~|-~{~Output[i] | i<b} and therefore S is consistent because ~|- ~S, i.e., the Actor machine output might be larger than b).

 

Parting thoughts

Message passing has fundamentally transformed the foundations and practice of computation since the initial conceptions of Turing and Church. Although 1^st order sentences can be useful (e.g. in SAT solvers), message passing illustrates why 1^st order logic cannot be the foundation for theories in Computer Science.

 

References

Alonzo Church. A set of postulates for the foundation of logic Annals of Mathematics. Series 2. 33 (2). 1932.

Ole-Johan Dahl and Kristen Nygaard. Class and subclass declarations IFIP TC2 Conference on Simulation Programming Languages. May 1967.

Carl Hewitt. Planner: A Language for Proving Theorems in Robots IJCAI-69.

Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI’73.

Carl Hewitt and John Woods assisted by Jane Spurr. Inconsistency Robustness, 2^nd Edition Studies in Logic. 2018.

Tony Hoare. Discrete Geometric Representation of Concurrent Program Execution Heidelberg Laureate Forum. September 23, 2016.

Robin Milner Elements of interaction: Turing award lecture CACM. January 1993.

Gordon Plotkin. A powerdomain construction SIAM Journal of Computing. September 1976.

Alan Turing. On Computable Numbers, with an Application to the Entscheidungsproblem Proceedings of the London Mathematical Society. November 1936.

 

Carl Hewitt is an emeritus professor of the Massachusetts Institute of Technology.  He is board chair of iRobust, an international scientific society for the promotion of the field of Inconsistency Robustness, and board chair of Standard IoT, an international standards organization for the Internet of Things, which is using the Actor Model to unify and generalize emerging standards for IoT.