Pourquoi l'état d'un FSM est-il traditionnellement noté

13

En enseignant comment implémenter les FSM à l'aide de circuits logiques synchrones, j'ai remarqué une coïncidence intrigante: dans le monde théorique CS et dans le monde de l'électrotechnique, "état" est généralement noté (et l'espace d'état ). J'ai d'abord posé une question sur EE.sx , mais en recherchant un peu ce sujet, j'ai trouvé que même le papier original de Turing de 1936 utilise pour désigner les états de la machine de Turing.qq 1 . . q nQq1..qn

Je me demande donc: à quand remonte cette convention, et pourquoi un "état" serait-il noté ?q

automata-theory ho.history-overview Gyom
la source
1
Si je devais deviner, je dirais que est l'abréviation de "configuration" (parce que et sont déjà liés à "constant"). Mais ce n'est qu'une supposition. c kqck
Jeffε
1
cette question intéressante sur le lien historique entre les machines de Turing et la réponse la plus votée des automates nie qu'il existe un lien historique direct entre une grande partie de la théorie des automates et le document Turings 1936. la réponse votée en bas souligne la similitude pratiquement identique du concept de table d'état.
vzn
1
Je pense que vous pouvez obtenir une meilleure réponse si vous la publiez sur MathOverflow. Ils ont plus d'experts en théorie de la calculabilité. Un autre bon endroit pour poser cette question est la liste de diffusion FOM qui compte de nombreux experts sur l'histoire de la calculabilité.
Kaveh

Réponses:

6

Dans son article de 1936 "SUR LES CHIFFRES INFORMATIQUES, AVEC UNE APPLICATION AU PROGRAMME ENTSCHEIDUNG" , Alan Turing a écrit:

"On peut comparer un homme en train de calculer un nombre réel à une machine qui n'est capable que d'un nombre fini de conditions q1, q2, .... qR qui seront appelées" m-configurations "

Il a donc souligné le fait que la machine a un nombre fini, discret (non continu) d'états ou de quantités. Pour moi, il s'agit d'une référence au terme Quanta utilisé en physique pour désigner des phénomènes variant non continuellement mais par "sauts" ou "quanta". Dans son article de 1950 "Computing Machinery and Intelligence", Alan Turing est plus explicite sur les "sauts" en parlant de "sauts soudains":

"Les ordinateurs numériques examinés dans la dernière section peuvent être classés parmi les" machines à états discrets. "Ce sont les machines qui se déplacent par sauts ou clics soudains d'un état bien défini à un autre."

Je pense donc qu'Alan Turing a utilisé q au lieu de s pour désigner un état machine pour souligner le fait que la machine état ne peut être que dans un ensemble de valeurs discrètes et finies comme les quanta en physique. Et depuis lors, la même notation est généralement utilisée.

Tarik FDIL
la source
2

Je ne suis pas sûr mais j'ai lu quelque part que Q signifie Quantum. Parce que nous savons que les automates fonctionnent dans un laps de temps discret. Un automate reste toujours dans un état dans un ensemble d'états finis, et commence même avec l'état initial q 0 . Un automate ne peut pas non plus être dans plus d'un état à la fois. Le mot quantique vient de la physique qui signifie quantité, quantité ou nombre.

Grijesh Chauhan
la source