<p>I am not sure but I read somewhere that <strong>Q means Quantum.</strong>  <strong>Because we know automata works in discrete time frame.</strong> An automaton always remains in some state in finite state set, and even starts with initial state q<sub>0</sub>. Also an automaton cannot be in more than one state at any instance of time. The word quantum comes from physics that means quantity, amount or number.     </p>

CC BY-SA 3.0
2012-12-23T14:24:57.657Z
2012-12-26T00:33:51.373Z
2012-12-26T00:33:51.373Z
Grijesh Chauhan
<p>In <a href="http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf">his 1936 paper "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM"</a>, Alan Turing wrote : </p>

<blockquote>
  <p>"We may compare a man in the process of computing a real number to
  machine which is only capable of a finite number of conditions q1, q2,
  .... qR which will be called " m-configurations"</p>
</blockquote>

<p>So he stressed the fact that the machine has a finite, discrete (not continuous) number of states or quantities. For me, it is a reference to the term Quanta used in physics to denote phenomena variating not continuously but by "leaps" or "quanta". In his <a href="http://www.thocp.net/biographies/papers/CMandI_Turing.htm">1950 article "Computing Machinery and Intelligence"</a> Alan Turing is more explicit about "leaps" speaking of "sudden jumps": </p>

<blockquote>
  <p>"The digital computers considered in the last section may be
  classified amongst the "discrete-state machines." These are the
  machines which move by sudden jumps or clicks from one quite definite
  state to another."</p>
</blockquote>

<p>So I think that Alan Turing used q instead of s to denote a machine state to stress the fact that the state machine can be only in a set of discrete and finite values like the quanta in physics. And since then, the same notation is generally used.</p>

CC BY-SA 3.0
2012-12-24T18:11:42.100Z
2012-12-24T18:11:42.100Z
Tarik FDIL
<p>While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is typically denoted $q$ (and the state space $Q$). I first <a href="https://electronics.stackexchange.com/questions/51625/">asked on EE.sx</a>, but then while researching a bit this topic, I found that even <a href="http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf" rel="nofollow noreferrer">Turing's original 1936 paper</a> uses $q_1..q_n$ to denote the states of the Turing machine. </p>

<p>So I wonder: <em>When</em> does this convention go back to, and <em>why</em> would a "state" be denoted $q$ ? </p>

CC BY-SA 3.0
2012-12-21T15:28:53.983Z
If I had to guess, I'd say $q$ is short for "configuration" (because $c$ and $k$ are already bound to "constant").  But that's just a guess.
Jeffε
CC BY-SA 3.0
2012-12-21T16:29:00.083Z
this interesting question on the [historical link between Turing machines and automata](http://cstheory.stackexchange.com/questions/10104/is-the-concept-of-the-turing-machine-derived-from-automata)'s top-voted answer denies there is a direct historical link between much automata theory and Turings 1936 paper. the bottom-voted answer points out the virtually identical similarity of the state table concept.
vzn
CC BY-SA 3.0
2012-12-24T21:47:49.743Z
I think you may get a better answer if you post it on MathOverflow. They have more computability theory experts. Another good place to ask this is FOM mailing list which has many experts on history of computability.
Kaveh
<automata-theory><ho.history-overview>
Why is the state of a FSM traditionally denoted $q$?
Gyom
# Why is the state of a FSM traditionally denoted $q$?

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

While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is typically denoted $q$ (and the state space $Q$). I first [asked on EE.sx](https://electronics.stackexchange.com/questions/51625/), but then while researching a bit this topic, I found that even [Turing's original 1936 paper](http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf) uses $q\_1..q\_n$ to denote the states of the Turing machine.

So I wonder: *When* does this convention go back to, and *why* would a "state" be denoted $q$ ?

**Tags:** automata-theory, ho.history-overview
> **Comments:**
> **username_1**: If I had to guess, I'd say $q$ is short for "configuration" (because $c$ and $k$ are already bound to "constant").  But that's just a guess.  
> **username_2**: this interesting question on the [historical link between Turing machines and automata](http://cstheory.stackexchange.com/questions/10104/is-the-concept-of-the-turing-machine-derived-from-automata)'s top-voted answer denies there is a direct historical link between much automata theory and Turings 1936 paper. the bottom-voted answer points out the virtually identical similarity of the state table concept.  
> **username_3**: I think you may get a better answer if you post it on MathOverflow. They have more computability theory experts. Another good place to ask this is FOM mailing list which has many experts on history of computability.  

---

## 2 answers

### Answer by username_5 on 2012-12-24. Score: 7 | Accepted answer

In [his 1936 paper "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM"](http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf), Alan Turing wrote :

> "We may compare a man in the process of computing a real number to
> machine which is only capable of a finite number of conditions q1, q2,
> .... qR which will be called " m-configurations"

So he stressed the fact that the machine has a finite, discrete (not continuous) number of states or quantities. For me, it is a reference to the term Quanta used in physics to denote phenomena variating not continuously but by "leaps" or "quanta". In his [1950 article "Computing Machinery and Intelligence"](http://www.thocp.net/biographies/papers/CMandI_Turing.htm) Alan Turing is more explicit about "leaps" speaking of "sudden jumps":

> "The digital computers considered in the last section may be
> classified amongst the "discrete-state machines." These are the
> machines which move by sudden jumps or clicks from one quite definite
> state to another."

So I think that Alan Turing used q instead of s to denote a machine state to stress the fact that the state machine can be only in a set of discrete and finite values like the quanta in physics. And since then, the same notation is generally used.


---

### Answer by username_4 on 2012-12-23. Score: 2

I am not sure but I read somewhere that **Q means Quantum.** **Because we know automata works in discrete time frame.** An automaton always remains in some state in finite state set, and even starts with initial state q0. Also an automaton cannot be in more than one state at any instance of time. The word quantum comes from physics that means quantity, amount or number.


---

