算術狀態機(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
- 簡介:算術狀態的抽象狀態機
- 所屬問題:可判定性理論
- 相關概念:狀態機,抽象狀態機等
歷史沿革,流程圖,
歷史沿革
抽象狀態機
一個抽象狀態機(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)