在無限自動機論中，主要研究信息加工系統和計算過程的數學模型、模擬、計算、識別和限制等問題。
基本介紹
- 中文名：無限自動機論
- 簡介：研究存儲量無限的離散數字系統功能和結構以及兩者關係的的理論
- 詞性：名詞
- 分類：理論
簡介,數學模型,模擬,識別器,資源限制,
簡介
研究存儲量無限的離散數字系統功能和結構以及兩者關係的的理論，是自動機論的次級學科。數字電路這類物理系統，只包含有限個記憶元件，它的存儲量是有限的。但是，稍複雜的算法，例如整數乘法所要求的存儲量往往是無限的。離散數字系統按照存儲量分為兩大類：存儲量有限的和存儲量無限的。後者的數學模型為各種無限自動機。在無限自動機論中，主要研究信息加工系統和計算過程的數學模型、模擬、計算、識別和限制等問題。
數學模型
從計算機的邏輯結構出發，抽象出它的數學模型，將一個自動機看作一個由控制器和它的外部環境組成的系統。控制器為一個有限自動機（見有限自動機論）。外部環境由一種數據結構刻劃。控制器從外部環境提取信息(輸入)，根據這些信息和控制器所處的內部狀態，產生改變外部環境的指令(輸出)並改變控制器的內部狀態。自動機一步一步地重複這種過程，對外部環境中的數據進行處理。按照外部環境及其與控制器的相互作用方式的不同，提出許多種不同的自動機。例如，一個單帶單頭圖靈機，它的外部環境可看作是一條可向一邊或兩邊延伸的、分成格子的帶子，帶子上存儲的數據可用字的有序對(xl,xr)表示，控制器可感知xr的左端字母,發出指令改寫這個字母,將xl的右端字母連線到xr的左端(左移一格),或將xr的左端字母連線到xl的右端(右移一格)。一個單暫存器機器的外部環境可看作是一個位數不受限制的暫存器,它存儲一個字x，控制器可感知x的左端字母,發出指令去掉x的左端字母,或在x的右端連線一個字母。自動機的外部環境可起存儲量無限的存儲器的作用,現實的計算機的存儲量是有限的,因此自動機是計算機的一種理想的數學模型。
另一種刻劃方法把一個自動機看作一個程式。例如作為圖靈機的一種變型提出來的 B機器。它是一個程式，指令系統由條件轉移、在注視格子上寫上記號*、 左移一格和右移一格所組成。一個無限制暫存器機器也是一個程式,指令系統包括：去掉第i暫存器中左端字母，在第i暫存器的右端連線一個字母，將第i暫存器清除為空字，傳送第i暫存器的內容到第j暫存器,無條件轉移,按照第i暫存器中左端字母轉移。
模擬
模擬指通過簡單的編碼在一個自動機上實現另一個自動機的功能。圖靈機和許多其他自動機都可以互相模擬。
在自動機的程式方向中，特別注意研究指令系統對計算能力的影響。例如 B機器或以擦指令代替寫指令的機器，雙計數器機器（指令系統為左移一格、右移一格和條件轉移），暫存器機器，它們的計算能力和圖靈機相同。但是，當條件轉移指令換為重複指令時，所計算的函式減少為原始遞歸函式（見可計算性理論）。
一個自動機的通用性指它能模擬任何自動機。A.M.圖靈構造出第一個通用自動機。C.E.仙農用機器狀態數與帶子字母數的乘積作為通用圖靈機簡單性的一種衡量標準。在60年代初已構造出一個7狀態4字母單帶通用圖靈機；在二維帶圖靈機的範圍內，還可改進到2狀態2字母。
識別器
圖靈機等一般自動機所識別的集恰是遞歸可枚舉集，推廣到非確定自動機的情形（即控制器是非確定有限自動機）不增加識別能力。識別能力介於有限自動機和一般自動機之間的機器，被認為更接近現實計算機而受到廣泛研究。已提出多種不同的自動機。對每種自動機，按照確定和非確定、數據結構的類型、機器與環境間相互作用的方式以及時間空間限制，可再分為許多類。每一類自動機所識別的集構成一類語言。主要研究的問題是各種限制類型的自動機識別集的刻劃、包含關係和代數性質。與形式語言有關的一個結果是，在喬姆斯基分層下的四類形式語言對應四類自動機的識別集：0型語言對應圖靈機可識別，1型語言對應非確定線性有界自動機可識別,2型語言對應非確定下推自動機可識別，3型語言對應有限自動機可識別。
資源限制
從實現的角度研究在計算時間、存儲空間或其他資源受到限制的情況下自動機的計算和識別能力。從有限自動機所計算的函式類F0齣發, 以 Fi中函式作為圖靈機計算的空間界限得出函式類Fi+1,則F0,F1,F2,…構成卡爾瑪初等函式(由四則運算與連加、連乘定義出的自然數上的函式)的一個分層,即Fi是Fi+1的真子集, 且所有Fi的和集為初等函式類。用阿克曼函式或增長速度類似的函式作為圖靈機等自動機的時間或空間界限，所得的函式類構成原始遞歸函式的一個分層；這些函式類與按照原始遞歸式（或聯立原始遞歸式）的嵌套重數分層的函式類一致。這些結果屬於亞遞歸分層問題。另一個問題為研究各類自動機在資源限制下所計算的函式類或識別集的類的包含關係。例如,k帶圖靈機的實時識別能力比 k-1帶圖靈機強；每條帶上具有多個讀寫頭的圖靈機可由每條帶上只有一個讀寫頭的圖靈機實時地模擬。
任一個可計算函式或可識別集，在計算時間和存儲空間受限制的情況下是否可計算或可識別的問題，從肯定方面涉及到好的算法的設計問題，從否定方面涉及到問題固有複雜性的下界估計問題。以回文識別為例，回文可由多帶圖靈機實時識別。將計算模型限制於單帶圖靈機的範圍，回文識別的固有時間複雜性（最壞情形）為平方級。這就是說，任何識別回文的單帶圖靈機T都存在常數C，使得幾乎所有回文為x,T 識別x所需的時間tT(x)不小於x的字長│x│的平方的C倍，即tT(x)≥C′|x|2；且這一下界不能再改進，因為存在識別回文的單帶圖靈機T′和常數C′,幾乎對所有字x都有
公式。對加法和反字的計算時間，也有類似回文的結果。
無限自動機的理論有助於理解計算過程的本質方面，在程式設計語言和編譯方面都有具體的套用。面向現實計算進行研究仍然是發展的趨勢。代數方法將受到更多的注意和發展。
