Lambda the Ultimate

Global State Machines are an inadequate foundation for computation (contra Dijkstra and Gurevich et. al.)

A principle limitation relates to the inability of Global State Machines to represent concurrency. See What is computation? Actor Model versus Turing's Model

       Global State Machine References

Andreas Blass, Yuri Gurevich, Dean Rosenzweig, and Benjamin Rossman (2007a)
   Interactive small-step algorithms I: Axiomatization
   Logical Methods in Computer Science. 2007.
Andreas Blass, Yuri Gurevich, Dean Rosenzweig, and Benjamin Rossman (2007b)
   Interactive small-step algorithms II: Abstract state machines and the characterization theorem
   Logical Methods in Computer Science. 2007.

Edsger Dijkstra.
   A Discipline of Programming 
   Prentice Hall. 1976.
Edsger Dijkstra and A.J.M. Gasteren.
   A Simple Fixpoint Argument Without the Restriction of Continuity
   Acta Informatica. Vol. 23. 1986.

A short 3 page workshop paper* submission. I've written to briefly describe Glitch. It has been a long journey from FRP signals to a model where I can actually write programs that I want to write.

Abstract:

Input changes are often handled by reactive and incremental constructs that are tedious to use and/or inexpressive, while changes to program code are not typically handled at all during execution, complicating support for "live programming." We propose that change in code and input should be managed automatically, similar to how garbage collection eliminates memory management as an explicit programmer concern. Our programming model, Glitch, realizes such managed time by progressively re-executing nodes of program execution when they become inconsistent due input/code state changes. Unlike many reactive models, Glitch supports expressive shared-state procedural programming, but with one caveat: operations on shared state must be undoable and commutative to ensure re-execution efficiency and eventual consistency. Still, complex programs like compilers can be written in Glitch using mundane programming styles.

* Apologies for using SkyDrive, it was just convenient. Use the download link and ignore the horrid Office 365 PDF viewer.