Por que o estado de um FSM é tradicionalmente indicado como

Enquanto ensinava como implementar FSMs usando circuitos lógicos síncronos, notei uma coincidência intrigante: tanto no mundo teórico do CS quanto no mundo da engenharia elétrica, "estado" é tipicamente denotado (e o espaço de estado Q ). Perguntei pela primeira vez no EE.sx , mas, ao pesquisar um pouco esse tópico, descobri que mesmo o artigo original de Turing de 1936 usa q 1 . . q n para indicar os estados da máquina de Turing.$q$$Q$$q_1..q_n$

Então, eu me pergunto: quando essa convenção volta e por que um "estado" seria indicado ?$q$

Em seu artigo de 1936, "SOBRE NÚMEROS COMPUTÁVEIS, COM APLICAÇÃO AO PROBLEMA DO ENTSCHEIDUNG" , Alan Turing escreveu:

"Podemos comparar um homem no processo de calcular um número real para uma máquina que só é capaz de um número finito de condições q1, q2, .... qR, que serão chamadas de" configurações m "

Então, ele enfatizou o fato de que a máquina possui um número finito e discreto (não contínuo) de estados ou quantidades. Para mim, é uma referência ao termo Quanta usado na física para denotar fenômenos que variam não continuamente, mas por "saltos" ou "quanta". Em seu artigo de 1950 "Computing Machinery and Intelligence", Alan Turing é mais explícito sobre "saltos" falando de "saltos repentinos":

"Os computadores digitais considerados na última seção podem ser classificados entre as" máquinas de estado discreto. "Essas são as máquinas que se movem por saltos ou cliques repentinos de um estado bastante definido para outro."

Então, acho que Alan Turing usou q em vez de s para denotar um estado de máquina para enfatizar o fato de que a máquina de estado pode estar apenas em um conjunto de valores discretos e finitos como os quanta na física. E desde então, a mesma notação é geralmente usada.

Não tenho certeza, mas li em algum lugar que Q significa Quantum. Porque sabemos que os autômatos funcionam em um período de tempo discreto. Um autômato sempre permanece em algum estado no conjunto de estados finitos e até começa com o estado inicial q ₀ . Além disso, um autômato não pode estar em mais de um estado a qualquer momento. A palavra quantum vem da física que significa quantidade, quantidade ou número.