6
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ I'm certain you can find at least a few Turing machine-inspired languages here. Whether you'd want to program with them is another matter. $\endgroup$ Dec 21, 2012 at 18:37
  • $\begingroup$ Thanks for directing me to that marvelous wiki, since I actually didn't know it existed until just now. I'm still holding out hope, however, for a language that someone actually finds useful. $\endgroup$ Dec 21, 2012 at 18:50

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Dec 27, 2012 at 18:23
  • $\begingroup$ 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. $\endgroup$ Dec 12, 2016 at 18:08
21
$\begingroup$

The short answer is no.

The long answer is that such languages are invented on a regular basis, but if they see any significant degree of use, for good semantic reasons they never remain in this mode for very long.

The basic problem is that it is very difficult to build programs compositionally using state machines. The modular construction of programs rests on two pillars: the variable, and the procedure abstraction. Variables let you define data in one place, and use it in another, and procedures let you parameterize a computation by some data. Without these features, it is extremely hard to build larger programs out of smaller programs.

State machines lack both of these features, and one of the first nontrivial theorems of computability (the $snm$ theorem) is the proof that Turing machines can implement them. However, the $snm$ theorem is too impractical to use as a practical calling convention, since it essentially says that the calling convention for programs is to pass arguments by passing strings which are interpreted as programs. This doesn't matter for the purposes of computability theory, but it ends up imposing order-of-magnitude slowdowns in practice (i.e., "interpretive overhead"). So people invariably add a primitive variable and procedure call mechanism to every language that sees serious use.

In fact, the lambda calculus demonstrates that you can build a Turing complete language out of nothing but variables and procedural abstractions. Unlike TMs, however, it's surprisingly practical to program in pure lambda calculus. The technical reason for this is that both lambda calculus and TMs form "closed categories" -- that is, they have the algebraic structure necessary to represent variables and procedures. However, the lambda calculus turns out to be basically a syntactic presentation (in the sense of generators and relations) of this algebraic structure, and so it makes it a lot more convenient to work with this structure.

$\endgroup$
2
  • 1
    $\begingroup$ This is a fantastic answer; thank you. I'm accepting Marzio De Biasi's answer because STRIPS looks like it's pretty close to what I wanted, but this is much appreciated as well. $\endgroup$ Dec 27, 2012 at 18:23
  • $\begingroup$ Have you heard of AWS's new "Step Function" feature? Per my comment on the accepted answer, it's essentially a state-based DSL where each state triggers a lambda function. My guess is that this will end up actually being a pretty good model for composing separate bits of functionality. Instead of using variables to transfer data, some kind of persistent backing storage (probably a database) will be used, and the lambdas themselves would, ideally, be stateless. The function-call abstraction would still exist, but only at the level of the lambdas themselves. $\endgroup$ Dec 12, 2016 at 18:15
3
$\begingroup$

This is slightly tangential, since Neil's lovely answer already addresses your question.

The difference between programming a Turing machine and what is usually considered a programming language is a topic that can be discussed at various levels of sophistication. Usually, we find it convenient to structure programs using variables, functions, function composition, etc. This is largely how we structure our mathematics. We tend to focus on the result of the computation rather than the mechanical process of how those results are derived.

There are situations when thinking in terms of state machines is convenient. For example when designing simple protocols, or describing access and locking policies for resources such as files, printers or memory. In such situations, it is easier to take a standard programming language with variables and functions and add support or explicitly encode a little state-machine behaviour. The word "behavioural" is often used in such contexts. You will find explicit state-based programming more often in Verilog/VHDL than in high-level software. There are also certain object oriented design patterns that enable state-based programming.

$\endgroup$
2
$\begingroup$

I am possibly too late on this, but an example of a state-based language is Protocol Modeling, for instance as described in:

Ashley T. McNeile, Ella E. Roubtsova: Aspect-Oriented Development Using Protocol Modeling. Transactions on Aspect-Oriented Software Development 7: 115-150 (2010).

This is a programming paradigm that expresses behavior using states and actions. It uses CSP (process algebra) style parallel composition to build a complete behavioral definition by composition of partial descriptions. This compositional style gives it an aspectual flavor, hence the publication cited above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.