<p>The short answer is no. </p>

<p>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. </p>

<p>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 <em>extremely</em> hard to build larger programs out of smaller programs. </p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2012-12-27T18:23:08.230Z
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
CC BY-SA 3.0
2016-12-12T18:15:57.760Z
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.
Kyle Strand
CC BY-SA 3.0
2012-12-21T20:05:56.500Z
2012-12-21T20:05:56.500Z
Neel Krishnaswami
<p>This is slightly tangential, since Neil's lovely answer already addresses your question.</p>

<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2012-12-21T22:19:51.130Z
2012-12-21T22:19:51.130Z
Vijay D
<p>I am possibly too late on this, but an example of a state-based language is Protocol Modeling, for instance as described in:</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-05-17T09:52:44.573Z
2013-05-17T09:59:58.893Z
2013-05-17T09:59:58.893Z
Ashley McNeile
<p>The state of a Turing machine is more or less the same thing as a line number in common programming languages (more precisely, the location of the command currently being executed). So yes, the <em>vast majority</em> of commonly used programmming languages are state-based, even though they do not explicitly employ this terminology.</p>

CC BY-SA 4.0
2024-04-18T10:34:42.497Z
2024-04-18T10:34:42.497Z
Emil Jeřábek
<p>I think that <a href="http://en.wikipedia.org/wiki/STRIPS">STRIPS</a> and other languages used in Automation Planning are very similar to a "<em>state-based</em>" programming language.</p>

<p>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).</p>

<p>A STRIP program is composed of:</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-12-27T18:23:52.720Z
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
CC BY-SA 3.0
2016-12-12T18:08:27.040Z
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.
Kyle Strand
CC BY-SA 3.0
2012-12-21T20:22:43.913Z
2012-12-21T20:22:43.913Z
Marzio De Biasi
<p>As anyone knows who has read Alan Turing's paper describing the Turing Machine (<em>On Computable Numbers, With an Application to the Entscheidungsproblem</em>), 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.</p>

<p>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.)</p>

<p>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?</p>

CC BY-SA 3.0
2012-12-21T18:37:54.297Z
I'm certain you can find at least a few Turing machine-inspired languages [here](http://esolangs.org/wiki/Main_Page). Whether you'd want to program with them is another matter.
C. A. McCann
CC BY-SA 3.0
2012-12-21T18:50:37.747Z
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
<pl.programming-languages><turing-machines>
Is there such a thing as a state-based programming language?
Kyle Strand
# Is there such a thing as a state-based programming language?

(Asked by: username_0 on 2012-12-21)

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?

**Tags:** pl.programming-languages, turing-machines
> **Comments:**
> **username_1**: I'm certain you can find at least a few Turing machine-inspired languages [here](http://esolangs.org/wiki/Main_Page). Whether you'd want to program with them is another matter.  
> **username_0**: 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.  

---

## 5 answers

### Answer by username_6 on 2012-12-21. Score: 6 | Accepted answer

I think that [STRIPS](http://en.wikipedia.org/wiki/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:**
> **username_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.  
> **username_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.  

---

### Answer by username_2 on 2012-12-21. Score: 24

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  

---

### Answer by username_3 on 2012-12-21. Score: 3

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.


---

### Answer by username_4 on 2013-05-17. Score: 2

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.


---

### Answer by username_5 on 2024-04-18. Score: 0

The state of a Turing machine is more or less the same thing as a line number in common programming languages (more precisely, the location of the command currently being executed). So yes, the *vast majority* of commonly used programmming languages are state-based, even though they do not explicitly employ this terminology.


---

