確定型圖靈機(deterministic Turing machine)一種圖靈機.指每一步都惟一確定的圖靈機.設M為一個圖靈機，則只要給M一個輸入，M便會以一種唯一確定的方式進行運行.即對M的同一個輸入，只有一種計算過程與之相應.這一點是由圖靈機程式的相容性條件所確定的(參見“圖靈機”)，這種圖靈機特稱為確定型圖靈機(參見“非確定型圖靈機”).
確定型圖靈機(deterministic Turing machine)一種圖靈機.指每一步都惟一確定的圖靈機.設M為一個圖靈機,則只要給M一個輸入,M便會以一種唯一確定的方式進行運行....
圖靈機分為確定圖靈機和不確定圖靈機。確定型圖靈機僅有一個轉移函式,轉移函式是從一個圖靈狀態到另一個圖靈狀態發出的指令。...
圖靈機在理論上能夠模擬現代數字計算機的一切運算, 可視為現代數字計算機的數學模型,是一種抽象的計算模型。交替式圖靈機(Alternating Turing Machine,ATM)是計算複雜...
圖靈機接受字的集合.設M為以J獷為字母表的圖靈機,在M的內部狀態集Q中指定一個子集Y里Q,Y中的內部狀態q:為接受狀態.對J獷上的任何字。,若M在輸入。後會...
線性有界自動機是一種圖靈機,是把計算限制在僅僅包含輸入的那一段帶上的圖靈機。可用作上下文有關語言的識別接受器。...
P問題是具有多項式算法的判定問題。這裡的P代表Polynomial。P問題就是可以有一個確定型圖靈機在多項式時間內解決的問題。即目前那些存在O(n), O(nk), O(nlogn)...
在計算複雜度理論內,時間譜系理論(Time hierarchy theorems)是一個有關圖靈機時間限制上面一個重要的理論。用不大正式的說法解釋,這理論告訴我們圖靈機在給予更多...
P類(P-class)一種特殊的類.指確定型圖靈機多項式時間可計算語言類.是由卡普(Karp , R.M.)於1972年首先引進的一個概念.設M為一個確定型圖靈機,若存在一個...
L也稱為LSPACE或DLOGSPACE,是計算複雜度理論中能被確定型圖靈機利用對數空間解決的判定問題集合。...
多項式時間可計算集是一種可計算的集合,指由多項式時間界確定型圖靈機所接受的集。...... 指由多項式時間界確定型圖靈機所接受的集.也即屍類中的集合(參見“屍...
L是NL的子集,NL是可以被非確定型圖靈機利用對數空間解決的判定問題集合。利用薩維奇定理的建構式證明,可得證NL包含在複雜度P之內,也就是可以被確定型圖靈機在...
複雜度類P包含所有那些可以由一個確定型圖靈機在多項式表達的時間內解決的問題;類NP由所有其肯定解可以在給定正確信息的多項式時間內驗證的決定問題組成,或者等效的...
因此為各類的抽象模型,我們可以定義不同的計算資源:在一個確定型圖靈機上是確定型時間;在非確定型圖靈機是非確定型時間,量子圖靈機則是量子時間……等等。輸入...
自動機理論,以及通過lambda演算進行函式式編程等計算問題,並為讀者自行探索打下了...5.1 確定型圖靈機 125 5.1.1 存儲 126 5.1.2 規則 127 5.1.3 確定...
P-NP I}}題(P-NP problem)亦稱P=? NP問題,計算複雜性理論以及計算機理論中最重要的一個未解決問題。它問在多項式時間界下,確定型圖機接受的語言類是與非...
在計算複雜性理論中,複雜性類NEXPTIME(有時稱為NEXP)是一組決策問題,可以通過使用時間2n的非確定性圖靈機來解決。...
自動機可分為有限自動機(即時序機)、後進先出自動機(即下推自動機)、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。...
例如一個問題如果在確定性圖靈機上所需時間不會超過一個確定的多項式(以輸入的長度為多項式的不定元),那么我們稱這類問題的集合為P(polynomial time Turing ...
與形式語言有關的一個結果是,在喬姆斯基分層下的四類形式語言對應四類自動機的識別集:0型語言對應圖靈機可識別,1型語言對應非確定線性有界自動機可識別,2型語言...
類似的,設n為輸入的長度,那我們可以定義“在確定性圖靈機上所需空間不超O(logn)的算法問題的集合”(即為L),“存在深度為O(logn),輸入的度(fan-in)為O(1...
2.8快速排序30 8.1.1非確定性圖靈機222 2.9線性時間選擇33 8.1.2P類與NP...各章配有難易適當的習題,分為理論分析型和套用實踐型兩種,理論分析型的習題側重...