Theoretical Computer Science
pl.programming-languages turing-machines
Updated Wed, 22 Jun 2022 05:06:08 GMT

Is there such a thing as a state-based programming language?


As anyone knows who has read Alan Turing's paper describing the Turing Machine (On Computable Numbers, With an Application to the Entscheidungsproblem), the syntax he uses is vastly different from that of modern languages (and closer to the densely symbolic mathematical writing of the time). This is not very surprising, since he wrote the paper about a decade before the first working electronic computer was finished and several decades before the first compiler was written. More interestingly, though, is the fact that the paradigm Turing uses seems pretty foreign as well. I would expect it to be procedural, but in fact it's what I would call "state-based": he describes a finite set of possible states in which the machine might find itself, and, given a particular state and an input value, he describes what actions the machine should take. In essence, then, the Turing machine is a finite state machine that has access to an infinite strip of rewritable memory locations. Since Turing proves that this machine is functionally equivalent to any other sufficiently powerful mechanical computational device, we can see that his state-based programming language can implement all the algorithms that other languages can implement.

As far as I know, however, there is no modern programming language that actually uses this paradigm. I suppose this is probably because it's a bit of a pain to wrap one's head around, and because it doesn't provide a very natural way of thinking about most algorithms, but I'd still be surprised if no one has at least tried something like this. And there may be some applications for which such a language would work extremely well. For instance, a processor can be represented quite directly as Turing's "universal" machine, which takes as input a coded representation of another machine and then performs the work that machine would perform; so might it be possible to design new processors by "compiling" something akin to Turing's language into a circuit layout for an FPGA? (True, the compiler might not come up with the optimal layout, and this approach might be too abstract to fully characterize the details of chip design, but this is just an example of something I think might work.)

So, my question is: does anyone know of any modern programming languages based on the original Turing machine language, or any languages that use a paradigm akin to this "state-based" paradigm?




Solution

I think that STRIPS and other languages used in Automation Planning are very similar to a "state-based" programming language.

The problem of finding if a STRIPS planning problem is satisfiable is PSPACE-complete, and in the (easy) proof you can see how it can simulate the behaviour of a Turing machine with a finite tape (LBA).

A STRIP program is composed of:

  • An initial state;
  • The specification of the goal states situations which the planner is trying to reach;
  • A set of actions. For each action, the following are included: preconditions (what must be established before the action is performed); postconditions (what is established after the action is performed)

There is no "procedural execution", but instead it is checked if a valid transition exists from the initial state to a state where the goal states are satisfied.





Comments (2)

  • +0 – Thank you! STRIPS looks pretty cool--I'll have to check it out, even if it's not likely to be of much practical value to me any time soon. — Dec 27, 2012 at 18:23  
  • +0 – AWS announced something called "Step Function" at their re:Invent conference this year that is essentially a way for composing individual lambda functions into a larger architecture. From a programming perspective, it's just a JSON-based DSL that describes a state-machine where each state triggers some lambda function. So I think that's another example of exactly this sort of paradigm. — Dec 12, 2016 at 18:08  


External Links

External links referenced by this document: