Dlaczego stan FSM tradycyjnie oznacza

13

Ucząc, jak implementować FSM przy użyciu synchronicznych obwodów logicznych, zauważyłem intrygujący zbieg okoliczności: zarówno w teoretycznym świecie CS, jak iw świecie elektrotechniki „stan” jest zwykle oznaczany jako (i przestrzeń stanu ). Najpierw zapytałem na EE.sx , ale potem, badając nieco ten temat, odkryłem, że nawet oryginalny papier Turinga z 1936 roku używa oznacza stany maszyny Turinga. $q$ $Q$ $q_1..q_n$

Zastanawiam się: kiedy wraca ta konwencja i dlaczego „stan” miałby być oznaczony ? $q$

automata-theory ho.history-overview

— Gyom
źródło

1

Gdybym musiał zgadywać, powiedziałbym, że

jest skrótem od „konfiguracji” (ponieważ

i

są już powiązane z „stałą”). Ale to tylko przypuszczenie.

q

$q$

c

$c$

k

$k$

— Jeffε

1

to interesujące pytanie na temat historycznego związku między maszynami Turinga i najczęściej głosowaną odpowiedzią automatów zaprzecza istnieniu bezpośredniego historycznego związku między teorią wielu automatów a publikacją Turingsa 1936. głosowana na dole odpowiedź wskazuje na praktycznie identyczne podobieństwo koncepcji tabeli stanów.

— vzn

1

Myślę, że możesz uzyskać lepszą odpowiedź, jeśli opublikujesz ją na MathOverflow. Mają więcej ekspertów teorii obliczeń. Innym dobrym miejscem do tego jest lista dyskusyjna FOM, która ma wielu ekspertów w dziedzinie historii obliczeń.

— Kaveh

6

W swoim artykule z 1936 r. „O LICZBACH WYLICZONYCH Z ZASTOSOWANIEM DO ENTSCHEIDUNGSPROBLEM” Alan Turing napisał:

„Możemy porównać człowieka w procesie obliczania liczby rzeczywistej do maszyny, która jest zdolna do spełnienia tylko skończonej liczby warunków q1, q2,… qR, które będą nazywane„ konfiguracjami m ”

Podkreślił więc fakt, że maszyna ma skończoną, dyskretną (nieciągłą) liczbę stanów lub wielkości. Dla mnie jest to odniesienie do terminu kwanty używanego w fizyce do oznaczania zjawisk zmieniających się nie w sposób ciągły, ale przez „skoki” lub „kwanty”. W swoim artykule z 1950 r. „Maszyny obliczeniowe i inteligencja” Alan Turing bardziej wyraźnie mówi o „skokach”, mówiąc o „nagłych skokach”:

„Komputery cyfrowe uwzględnione w ostatniej sekcji można zaliczyć do„ maszyn o stanie dyskretnym ”. Są to maszyny, które przemieszczają się przez nagłe skoki lub kliknięcia z jednego całkiem określonego stanu do drugiego.”

Myślę więc, że Alan Turing użył q zamiast s do oznaczenia stanu maszyny, aby podkreślić fakt, że maszyna stanu może mieć tylko zbiór dyskretnych i skończonych wartości, takich jak kwanty w fizyce. I od tego czasu powszechnie stosuje się ten sam zapis.

— Tarik FDIL
źródło

2

Nie jestem pewien, ale gdzieś przeczytałem, że Q oznacza Kwant. Ponieważ wiemy, że automaty działają w dyskretnych ramach czasowych. Automat zawsze pozostaje w pewnym stanie w ustawionym stanie skończonym, a nawet rozpoczyna się od stanu początkowego q ₀ . Również automat nie może znajdować się w więcej niż jednym stanie w żadnym momencie. Słowo kwant pochodzi od fizyki, która oznacza ilość, ilość lub liczbę.

— Grijesh Chauhan
źródło