交替圖靈機（alternating Turing machine）是2018年公布的計算機科學技術名詞。
交替圖靈機（alternating Turing machine）是2018年公布的計算機科學技術名詞。定義 類似於非確定型圖靈機。按如下方式定義的計算模型：每一個轉移函式有兩個選擇，每一個內部狀態有一個標籤或，中間格局由它的狀態標籤彐及∀，下一個...
圖靈機，又稱圖靈計算機，是一個抽象的機器。它由英國數學家艾倫・麥席森・圖靈(1912―-1954年)於1936年提出的一種抽象的計算模型，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人類進行數學運算。圖靈機有一條...
complexity class）是2018年公布的計算機科學技術名詞。定義 在多項式時間內一切交替圖靈機所接受的語言做成的類，記為AP。已經證明AP = PSPACE，即交替多項式時間複雜性類與多項式空間複雜性類相同。出處 《計算機科學技術名詞 》第三版。
交替對數空間複雜性類（alternating logspace complexity class）是2018年公布的計算機科學技術名詞。定義 在對數空間交替圖靈機所接受的語言做成的類，記為AL。已經證明AL = P，即交替對數空間複雜性類與多項式時間複雜性類相同。出處 《...
《具有較小空間複雜性的交替式下推自動機的研究》是依託中國海洋大學，由徐建良擔任項目負責人的青年科學基金項目。 中文摘要 研究具有較小空間複雜性的交替式下推自動機是非常有意義的，因為交替式下推自動機是一個比交替式圖靈機更簡單...
交替時間複雜性是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。定義 交替圖靈機的時間複雜性。令 M 是一個交替圖靈機，對函式 t ∶N→N，稱 M 是 t(n) 時間的交替圖靈機，如果對每一個輸入，和每一個轉移函式的...
交替空間複雜性是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。定義 交替圖靈機的空間複雜性。令 M 是一個交替圖靈機，對函式 s ∶N→N，稱 M 是 s(n) 空間的交替圖靈機，如果對任何輸入，任何轉移函式的選擇系列，...
1.8 非確定圖靈機 26 1.9 命題邏輯 29 1.10 謂詞邏輯 32 1.11 計算的邏輯刻畫 34 1.12 時間譜系定理 37 1.13 間隙定理 41 1.14 神諭圖靈機 42 1.15 歸約 43 1.16 空間複雜性類 45 1.17 對數空間類 49 1...
