圖靈機分為確定圖靈機和不確定圖靈機。確定型圖靈機僅有一個轉移函式,轉移函式是從一個圖靈狀態到另一個圖靈狀態發出的指令。
相關詞條
- 確定型圖靈機
確定型圖靈機(deterministic Turing machine)一種圖靈機.指每一步都惟一確定的圖靈機.設M為一個圖靈機,則只要給M一個輸入,M便會以一種唯一確定的方式進行運行....
- 確定圖靈機
圖靈機分為確定圖靈機和不確定圖靈機。確定型圖靈機僅有一個轉移函式,轉移函式是從一個圖靈狀態到另一個圖靈狀態發出的指令。...
- 非確定型圖靈機
非確定型圖靈機(non-deterministic Turingmachine)確定型圖靈機的一種推廣。設P為一個由圖靈機指令組成的有窮集合,P不一定滿足相容性條件,如果把P作為程式,依類似...
- 圖靈機
所謂的圖靈機就是指一個抽象的機器,它有一條無限長的紙帶,紙帶分成了一個一個的小方格,每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組...
- 圖靈機接受語言
圖靈機接受字的集合.設M為以J獷為字母表的圖靈機,在M的內部狀態集Q中指定一個子集Y里Q,Y中的內部狀態q:為接受狀態.對J獷上的任何字。,若M在輸入。後會...
- 交替式圖靈機
圖靈機在理論上能夠模擬現代數字計算機的一切運算, 可視為現代數字計算機的數學模型,是一種抽象的計算模型。交替式圖靈機(Alternating Turing Machine,ATM)是計算複雜...
- 非確定性
所謂非確定性是指在理論計算機科學中,針對各種計算機器模型(自動機),在每一時刻,根據當時的狀態和輸入,若機器有多個動作可供選擇時,則稱機器為非確定性的;相反,...
- 時間譜系理論
在計算複雜度理論內,時間譜系理論(Time hierarchy theorems)是一個有關圖靈機時間限制上面一個重要的理論。用不大正式的說法解釋,這理論告訴我們圖靈機在給予更多...
- 多項式時間可計算集
多項式時間可計算集是一種可計算的集合,指由多項式時間界確定型圖靈機所接受的集。... 指由多項式時間界確定型圖靈機所接受的集.也即屍類中的集合(參見“屍類...
- 形式語言與自動機及程式設計
陸玲、周書民編著的《形式語言與自動機及程式設計》介紹了喬姆斯文法體系的四類文法及相應的實例,以及無限自動機、下推機、圖靈機及相應買例。利用VC++6.0實現了...
- LSPACE
L也稱為LSPACE或DLOGSPACE,是計算複雜度理論中能被確定型圖靈機利用對數空間解決的判定問題集合。...
- 自動機理論與套用
第4部分 圖靈機與不可確定性第17章 圖靈機 25917.1 定義、符號與例子 25917.1.1 什麼是圖靈機 25917.1.2 圖靈機編程 262...
- P類(P-class)
P類(P-class)一種特殊的類.指確定型圖靈機多項式時間可計算語言類.是由卡普(Karp , R.M.)於1972年首先引進的一個概念.設M為一個確定型圖靈機,若存在一個...