自動機論
正文
研究離散數字系統的功能和結構以及兩者關係的數學理論。離散數字系統的時間坐標是離散的，表征系統的變數的值是數字量。數字電路、數字信道、自動電話交換機、數字計算機、程式和算法是數字系統的一些實例。在自動機論中，自動機是一個數學概念，作為離散系統的抽象模型。給定自動機的功能描述，綜合出具有這種功能的自動機的結構；給定自動機的結構，分析它的功能，這就是自動機的綜合和分析問題，它是自動機論的典型研究課題。歷史和發展 19世紀中期，英國G.布爾用數學方法研究思維規律的問題建立了邏輯代數，後人稱之為布爾代數。1935～1938年，蘇聯В.И.肖斯塔科夫和美國C.E.仙農，獨立地套用布爾代數於繼電器接點電路的分析和綜合,形成了開關網路理論。1936年,為了對能行性、機械過程或算法進行精確的數學描述，英國A.M.圖靈提出一種理想計算機，後人稱之為圖靈機。1944年，W.S.麥克卡洛和W.匹茨用數理邏輯方法研究神經網路。40年代中期出現電子計算機以後，美籍匈牙利數學家J.諾伊曼在1948年提出建立自動機的一般邏輯理論，對各種人造自動機和天然自動機進行比較性研究，探索其共同規律。他還研究了自動機的自繁殖和自恢復問題。諾伊曼被認為是自動機論的創立者。
受計算機的影響，50年代初，開關網路的研究重點轉移到一般的邏輯網路，特別是門電路類型開關網路。1954年前後形成了時序機（即有限自動機）這一重要數學概念。同時，從數字計算機的一種理想的數學模型的角度，開始對圖靈機深入研究。1956年《自動機研究》論文集的出版，標誌著自動機論已形成為一門獨立的學科。
50年代以來，自動機論有了很大的發展。有限自動機的理論得到廣泛深入和系統的研究，成為自動機論中最成熟的領域，並在許多工程上得到套用。無限自動機的理論主要是處理計算過程，對圖靈機理論的研究一直在持續進行，對更自然的計算機數學模型的探索和在資源限制下自動機的功能的研究也有了較大的進展。機率自動機主要是機率有限自動機的理論，在1963年後有了較大發展。60年代後期以來，細胞自動機主要是在生物學和大規模積體電路技術的基礎上成為自動機論中一個活躍的領域。同時，在抽象自動機方面，也開展了研究。
學科內容 自動機論可分為五個次級學科。
有限自動機論 包括開關網路理論，主要研究對象為繼電器接點電路、數字電路、理想神經網路這類存儲量有限的自動機。主要的研究問題是綜合和分析問題。一種典型的問題提法是：研究由某種數學語言陳述的功能出發，設計出滿足要求的有限自動機和實現它的邏輯網路的系統方法。這涉及到功能描述數學語言、狀態化簡、狀態賦值、布爾函式化簡、多值邏輯、組合複雜性和分解等問題的研究。另一個重要方向是1959年開始研究的可逆性問題，主要研究判別、求逆和結構問題。自動機作為轉換器將輸入序列變換為輸出序列，沒有輸入的自動機可作為序列產生器，沒有輸出的自動機可作為序列識別器。有限自動機作為序列產生器是50年代中期開始深入研究的一個方向，代數方法得到了很好的套用。有限自動機作為序列識別器的研究方向，較早地建立了比較完善的理論。
無限自動機論 主要研究對象為算法和理想計算機這種存儲量不受限制的自動機。研究的問題包括探索計算機和計算過程的數學模型，以及各種模型之間的關係。60年代初開始的一個重要研究問題是，在計算時間、存儲空間和機器規模等資源受限制的情況下，自動機所計算的函式類和識別集的類的刻劃、包含關係和代數性質。另一個從50年代末開始活躍的領域是，將自動機識別集作為形式語言的一種刻劃方法，對各種限制類型自動機的功能的研究。
機率自動機論 主要研究對象是在環境或內部具有隨機因素的(有限或無限)自動機。機率有限自動機（即隨機時序機）是1948年仙農提出的，作為噪聲信道的一種模型。60年代後開始系統地發展，主要是推廣確定自動機的結果，研究實現、化簡、識別和穩定性等問題。在自恢復自動機方面，50年代初諾依曼研究的由不可靠元件構造可靠系統的方向，到70年代發展為容錯計算這一活躍的研究領域。另一個方向是對各種機率自動機所識別的語言的研究。
細胞自動機論 主要研究對象是由許多互相連線的小自動機並行運算形成的大自動機。這項研究始於諾依曼對自繁殖自動機的研究。從他提出的細胞空間概念發展出許多研究方向。與計算機有關的一個方向是具有細胞類型的並行計算機模型的研究，這些研究已套用到一些並行計算機的體系設計中。70年代活躍起來的另一個方向面向大規模積體電路技術，研究具有一致結構的各種細胞自動機的分析、綜合和容錯等問題。在發育生物學方面，1968年荷蘭生物學家A.林頓梅伊爾推廣了諾依曼的細胞空間概念，提出了一種動態細胞自動機的數學結構，通常稱之為L系統，用以描述多細胞組織的發育過程。1974年以來，L-系統的理論是一個十分活躍的研究領域。
抽象自動機論 將自動機作為一種數學系統，研究它的一般數學性質。一個重要的研究方向為自動機的半群理論，它為有限自動機的分解問題提供了工具。另一個方向是研究範疇上自動機，目標是建立一個關於有限自動機、線性控制系統、樹自動機、機率自動機和拓撲自動機等的統一理論。
與其他學科的關係和套用 自動機論是古老的數學學科的一個新興分支。在它的形成和發展過程中，其他數學分支特別是數理邏輯起了很大的作用。自動機論和數理邏輯的一些領域交叉重疊，例如可計算性理論和無限自動機的功能理論都以算法為主要研究對象，但它們的側重點不同。
自動機論與形式語言理論關係密切。一方面自動機作為形式語言的一種主要描述方法，另一方面形式文法也可作為自動機識別集的一種描述方法。自動機論與計算複雜性理論的一些領域交叉重疊，例如組合複雜性和計算複雜性。自動機論是計算機科學的基礎理論中較早形成的部分。
自動機論又是控制論的一部分。自動機，包括有限自動機、圖靈機和理想神經網路，是控制論系統的一種模型。自適應、自學習、自恢復和自繁殖自動機的研究，是典型的控制論問題。自動機論與控制論的其他部分關係也很密切。例如，自動機論與控制理論中的許多結果是類似的，這種類似性成為抽象自動機研究的一個出發點。
自動機論的形成受自動控制、計算機和數字通信技術的推動，它的成果又套用於這些技術學科中。自動機論探索和提供各種數字電路綜合分析的系統方法。細胞自動機對並行計算機設計思想產生了明顯的影響。自動機作為一種基本工具用於高級程式語言的編譯設計。線性自動機作為偽隨機序列產生器用途廣泛。可逆自動機用於通信編碼。
自動機論的形成和發展的部分原因，是對生物系統進行一般性刻劃，例如在神經網路和自繁殖自動機方面的工作。基於多細胞組織的發育是執行一種“發育程式“的觀念，自動機也用於研究生物發育。
參考書目
陶仁驥著：《有限自動機的可逆性》,科學出版社,北京，1979。
C.E.申南、J.麥克卡賽編，陳中基編譯：《自動機研究》，科學出版社，北京，1963。(C.E.Shannon and J.McCarthy eds.,Automata Studies, Princeton Univ. Pr., Princeton, N.J.,1956.)
M.A.Arbib, Theories of Abstract Automata, Prentice-Hall,Englewood Cliffs, N.J., 1969.
