算術狀態機(Arithmetical ASM，AASM)是算術狀態的抽象狀態機，有的書籍也將算術狀態機寫為ASM(algorithmic state machine)。算術狀態機(algorithmic state machine)(ASM)表示法是一種類似流程圖的嵌套If-then-else語句的等效形式，已經使用了不止25年，所謂的ASM圖表(ASM chart)，由Hewlett-Packard實驗室的Thomas E.Osborne首先提出的，後來又由Osborne的同事Christopher R.Clare在((Designing Logic Systems Using State Machines》(McGraw-Hill，1973)一書中做了進一步的發展。
基本介紹
- 中文名：算術狀態機
- 外文名：algorithmic state machine
- 簡寫：ASM，AASM
- 簡介：算術狀態的抽象狀態機
- 所屬學科：數學
- 所屬問題：可判定性理論
- 相關概念：狀態機，抽象狀態機等
基本介紹,抽象狀態機,算術狀態,算術狀態機,Minsky機,算術狀態機表,基本介紹,ASM表符號,
基本介紹
抽象狀態機
一個抽象狀態機(ASM)是由以下構成的：
(1)一個代數狀態集合S，它的同構映射是封閉的，且匹配於函式符號
。
(2)一個初始狀態集合
，
的同構映射也是封閉的。
(3)一個程式P，它由有窮多的指令構成，每個指令採取以下“If···then···”的“條件-執行”形式：
If p then t：=u
其中：“代數狀態”指常元(代數)與函式符號的的匹配，如3+2；p是為真的程式；t和u都是項(常元)：“：=”表示一個賦值(t值更新為“u)。
一個抽象狀態機可以描述計算。給定一個狀態
，程式p的執行將導致的一次新的賦值。
算術狀態
算術狀態由以下規定確定：
定義域為自然數
，其中
表示“未定義”。
運算(操作)包括0，+1，+，－，×，÷，=，>，邏輯運算，動態(運行的)的函式。
規定n×m=0|n<m(小數減大數均等於0)；n÷0=(禁止0作除數)；除法的餘數均被省略。這樣保證每一次加、減、乘、除運算結果都是合法的且封閉於定義域內。
算術狀態機
算術狀態機(Arithmetical ASM，AASM)是算術狀態的抽象狀態機，有時也將算術狀態機寫為ASM(algorithmic state machine)。
算術狀態機(algorithmic state machine)(ASM)表示法(它是一種類似流程圖的嵌套If-then-else語句的等效形式)已經使用了不止25年。所謂的ASM圖表(ASM chart)，由Hewlett-Packard實驗室的Thomas E.Osborne首先提出的，後來又由Osborne的同事Christopher R.Clare在((Designing Logic Systems Using State Machines》(McGraw-Hill，1973)一書中做了進一步的發展。用ASM圖表設計和綜合的方法，還可以在許多關於數學設計的課本中棧到，包括本書的前兩個版本。
Minsky機
Minsky機包括有窮數量的暫存器
，暫存器中的數據由程式操作；程式由一系列指令構成；一條指令陳述對一個暫存器的一次操作，並指示下一個指令；操作只包含4種：
(清空暫存器，求後繼，不為0則減1，否則跳到第n號指令，停機)，如圖1所示。
圖1 Minsky機(程式機)的結構算術狀態機表
基本介紹
算術狀態機表(algorithmic state machine(ASM) chart)有意構成類似於電腦程式的流程圖，使用了相對比較少的符號，邏輯上互相連線，表示狀態機從一個狀態到下一個狀態的進程。這對系統的預期動作提供了一步一步的詳細描述。
ASM表符號
方框圖用來表示指定的系統狀態、常常在矩形框旁邊標出助記符為狀態命令，在矩形框內部列出的是當狀態機在特定狀態時可能產生的輸出。這些輸出叫無條件輸出。狀態機嚴格地按照指定狀態存在一個時鐘周期。
圖2所示矩形框，表示狀態AA，而系統是在此狀態中，它將產生輸出OUT1和XX。如果狀態機以預定方式一個狀態一個狀態的進行，與任何輸入無關。狀態用直線段連線如圖2所示。
圖2（a）
圖2(b)在這種情況下，狀態J存在一個時鐘周期之後，當下一個時鐘脈衝到達時，狀態機的狀態移到狀態K。注意這種情況下輸出的變化。
菱形或擴展菱形用來表示條件分支，次態假設決定於一個或多個輸入變數的值。布爾函式與這些表示在擴展菱形內部變數有關，而分支路徑和相應的函式值一起被標出。菱形本身叫決策框並且不會被分離標識出來。
在ASM表中線段表示在圖3中，狀態機在狀態J，將在下一個時鐘脈衝進入狀態K還是狀態L，決定於布爾函式A+B是(TRUE)真還是(FALSE)假。處於狀態J的狀態機在時鐘周期內做出這個決策是很重要的。從這個意義上看，決策框屬於被輸入的狀態。
圖3橢圓形用來表示條件輸出，不只取決於狀態，而且也與一個或多個輸入的狀態有關。它與決策框的退出有關，因此叫條件輸出框。
圖4所示表1狀態機在狀態J開始，在此時鐘周期內，布爾函式A(B+C)被估計出。在時鐘周期內無條件地產生輸出OUT1，在此時OUT2或OUT3也將產生取決於布爾函式的估值。在圖4中，OUT2有條件地產生狀態J，而無條件地產生狀態K。注意：決策框如何確定輸出產生，在給定狀態下同時也確定了次態。還要注意：在圖中實際影響這些決策產生的只是那些輸入。在改變的狀態被確定之前沒有必要對所有輸入求值。
圖4