Warum wird der Zustand eines FSM traditionell als

12

Während ich unterrichtete, wie FSMs unter Verwendung synchroner logischer Schaltungen implementiert werden, fiel mir ein faszinierender Zufall auf: Sowohl in der theoretischen CS-Welt als auch in der Welt der Elektrotechnik wird "Zustand" typischerweise als (und der Zustandsraum Q ) bezeichnet. Ich zum ersten Mal auf EE.sx gefragt , aber dann , während ein bisschen dieses Thema Forschung, fand ich , dass auch Turings Original 1936 Papier Anwendungen q 1 . . q n , um die Zustände der Turing-Maschine zu kennzeichnen.qQ.q1..qn

Ich frage mich also: Wann geht diese Konvention zurück und warum wird ein "Staat" als ?q

automata-theory ho.history-overview Gyom
quelle
1
Wenn ich raten müsste, würde ich sagen, dass für "configuration" steht (weil c und k bereits an "constant" gebunden sind). Aber das ist nur eine Vermutung. qck
Jeffs
1
Diese interessante Frage zur historischen Verbindung zwischen Turing-Maschinen und der am häufigsten gewählten Antwort von Automaten leugnet, dass eine direkte historische Verbindung zwischen viel Automatentheorie und dem Artikel von Turings 1936 besteht. Die unterste Antwort weist auf die praktisch identische Ähnlichkeit des Zustandstabellenkonzepts hin.
vzn
1
Ich denke, Sie erhalten möglicherweise eine bessere Antwort, wenn Sie sie auf MathOverflow veröffentlichen. Sie haben mehr Experten für Berechenbarkeitstheorie. Ein weiterer guter Ort, um dies zu erfragen, ist die FOM-Mailingliste, die viele Experten für die Geschichte der Berechenbarkeit hat.
Kaveh

Antworten:

5

In seiner 1936 erschienenen Arbeit "ON COMPUTABLE NUMBERS, WITH A APPLICATION TO THE ENTSCHEIDUNGSPROBLEM" schrieb Alan Turing:

"Wir können einen Mann vergleichen, der gerade dabei ist, eine reelle Zahl mit einer Maschine zu berechnen, die nur eine endliche Anzahl von Bedingungen q1, q2, ... qR kann, die als" m-Konfigurationen "bezeichnet werden."

Deshalb betonte er die Tatsache, dass die Maschine eine endliche, diskrete (nicht kontinuierliche) Anzahl von Zuständen oder Größen hat. Für mich ist es eine Bezugnahme auf den Begriff Quanta, der in der Physik verwendet wird, um Phänomene zu bezeichnen, die sich nicht kontinuierlich ändern, sondern durch "Sprünge" oder "Quanten". In seinem 1950 erschienenen Artikel "Computing Machinery and Intelligence" geht Alan Turing expliziter auf "Sprünge" ein und spricht von "plötzlichen Sprüngen":

"Die im letzten Abschnitt betrachteten Digitalcomputer können unter den" diskreten Automaten "klassifiziert werden. Dies sind die Automaten, die sich durch plötzliche Sprünge oder Klicks von einem ganz bestimmten Zustand in einen anderen bewegen."

Ich denke also, dass Alan Turing q anstelle von s verwendet hat, um einen Maschinenzustand zu bezeichnen, um die Tatsache hervorzuheben, dass die Zustandsmaschine nur in einer Menge von diskreten und endlichen Werten wie den Quanten in der Physik vorliegen kann. Und seitdem wird im Allgemeinen dieselbe Notation verwendet.

Tarik FDIL
quelle
2

Ich bin mir nicht sicher, aber ich habe irgendwo gelesen, dass Q Quantum bedeutet. Weil wir wissen, dass Automaten in einem diskreten Zeitrahmen arbeiten. Ein Automat bleibt immer in einem bestimmten Zustand und beginnt sogar mit dem Anfangszustand q 0 . Außerdem kann sich ein Automat zu keinem Zeitpunkt in mehr als einem Zustand befinden. Das Wort Quantum kommt aus der Physik und bedeutet Menge, Menge oder Zahl.

Grijesh Chauhan
quelle