Mientras enseñaba cómo implementar FSMs utilizando circuitos lógicos sincrónicos, noté una coincidencia intrigante: tanto en el mundo teórico de CS como en el mundo de la ingeniería eléctrica, el "estado" se denota típicamente (y el espacio de estado ). Primero pregunté sobre EESX , pero luego, mientras investigaba un poco sobre este tema, descubrí que incluso el artículo original de Turing de 1936 usa para denotar los estados de la máquina de Turing.Q q 1 . . q n
Así que me pregunto: ¿ cuándo vuelve esta convención y por qué se denota un "estado" ?
Respuestas:
En su artículo de 1936 "SOBRE NÚMEROS COMPUTABLES, CON UNA APLICACIÓN AL PROBLEMA DE ENTSCHEIDUNGS" , Alan Turing escribió:
Entonces enfatizó el hecho de que la máquina tiene un número finito, discreto (no continuo) de estados o cantidades. Para mí, es una referencia al término Quanta usado en física para denotar fenómenos que varían no continuamente sino por "saltos" o "quanta". En su artículo de 1950 "Maquinaria de computación e inteligencia", Alan Turing es más explícito sobre los "saltos" al hablar de "saltos repentinos":
Así que creo que Alan Turing usó q en lugar de s para denotar un estado de máquina para enfatizar el hecho de que la máquina de estados solo puede estar en un conjunto de valores discretos y finitos como los cuantos en física. Y desde entonces, generalmente se usa la misma notación.
fuente
No estoy seguro, pero leí en alguna parte que Q significa Quantum. Porque sabemos que los autómatas funcionan en un marco de tiempo discreto. Un autómata siempre permanece en algún estado en un conjunto de estados finitos, e incluso comienza con el estado inicial q 0 . Además, un autómata no puede estar en más de un estado en ningún momento. La palabra cuántica proviene de la física que significa cantidad, cantidad o número.
fuente