Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  C. A. McCann Dec 21 '12 at 18:37
    
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. –  Kyle Strand Dec 21 '12 at 18:50

4 Answers 4

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  Kyle Strand Dec 27 '12 at 18:23

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.

share|improve this answer
1  
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. –  Kyle Strand Dec 27 '12 at 18:23

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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