確定性圖靈機（deterministic Turing machine）是1993年公布的數學名詞。
基本介紹
- 中文名：確定性圖靈機
- 外文名：deterministic Turing machine
- 所屬學科：數學
- 公布時間：1993年
公布時間,出處,
公布時間
1993年，經全國科學技術名詞審定委員會審定發布。
出處
《數學名詞》第一版。
確定性圖靈機
相關詞條
- 圖靈機
圖靈機，又稱圖靈計算機，是一個抽象的機器。它由英國數學家艾倫・麥席森・圖靈(1912―-1954年)於1936年提出的一種抽象的計算模型，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人類進行數學運算。圖靈機有一條...
- 自動化理論-圖靈機
圖靈機是由英國數學家圖靈（A.M.Turing，1912~1954）在1936年提出的一種計算模型。同遞歸函式和λ-演算相比較，圖靈機的結構和運行同希爾伯特提出的形式系統更為接近，只不過圖靈機並不是（入希爾伯特所希望的那樣）用於判定命題的正確性...
- 非確定型圖靈機
非確定型圖靈機(non-deterministic Turingmachine)確定型圖靈機的一種推廣。設P為一個由圖靈機指令組成的有窮集合，P不一定滿足相容性條件，如果把P作為程式，依類似於確定型圖靈機的模式進行運行，則可能會在某個時刻有兩條或更多的...
- LSPACE
L也稱為LSPACE或DLOGSPACE，是計算複雜度理論中能被確定型圖靈機利用對數空間解決的判定問題集合。簡介 L也稱為LSPACE或DLOGSPACE，是計算複雜度理論中能被確定型圖靈機利用對數空間解決的判定問題集合。對數空間是指與輸入規模成對數大小...
- P類問題
所謂P類和NP類，都是指問題的集合。由於確定的圖靈機可以看作不確定的圖靈機的一種特殊情形，因此這兩類問題的集合之間存在子集關係，即P屬於NP。NP完全問題 NP-完全問題( Np-complete problem)是計算複雜性理論中最重要的一部分內容...
- Cook-Levin理論
Cook-Levin定理，也稱為Cook定理，表明布爾可滿足性問題是NP完全的。 也就是說，NP中的任何問題都可以通過確定性圖靈機在多項式時間內減少到確定布爾公式是否可滿足的問題。該定理以史蒂芬庫克和列昂尼德萊文命名。定義 如果可以在多項式時間...
- P/NP問題
複雜度類P包含所有那些可以由一個確定型圖靈機在多項式表達的時間內解決的問題；類NP由所有其肯定解可以在給定正確信息的多項式時間內驗證的決定問題組成，或者等效的說，那些解可以在非確定圖靈機上在多項式時間內找出的問題的集合。很可能...
- ZPP
字元串w可以被認為是會員證明。 在可以有效驗證的短期證明（長度受輸入大小的多項式約束）的情況下（V是一個多項式時間確定性圖靈機），字元串w被稱為見證。注釋：該定義非常不對稱。 x在x中的證明是單個字元串。 x不在X中的證明是...
- 計算複雜性理論(理論計算機科學分支學科)
概括的說，他們證明了，有一個通用的過程對NP中任意語言在非確定性圖靈機上運行歷史用布爾表達式來編碼，使得該布爾表達式是可滿足的，若且唯若該運行歷史是對給定輸入，接受該輸入的。這樣，我們就有了第一個被證明是NP完備的問題。在...
- NL完全
在全體判定問題中，NL類包含了那些可以用非確定型圖靈機在對數空間內解決的問題。這裡的圖靈機要求有一條唯讀輸入帶，和另一條空間上限與輸入長度的對數成比例的讀寫帶。類似地，L類包含了可以用同樣結構的確定型圖靈機解決的判定問題。
- 時間譜系理論
圖靈機 圖靈機（英語：Turing machine），又稱確定型圖靈機，是英國數學家艾倫·圖靈於1936年提出的一種抽象計算模型，其更抽象的意義為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
- 丘奇定理
量子計算機是一個實現計算的物理裝置，是遵循量子物理學規律運行的物理系統，而且量子計算機是一種建立在量子圖靈機基礎上的現代計算機。通用圖靈機的算法是完全確定性的，在這種確定性算法中，當圖靈機的當前讀寫頭的狀態和當前存儲單元內容...
- 丘奇論題
比如，一個懸而未決的問題是我們無法確定量子力學（quantum mechanical）的事件是否圖靈可計算的，儘管諸如量子圖靈機之類的嚴格模型實際上等價於確定性圖靈機（但並不一定在效率上等價）。約翰·盧卡斯和名氣更大一點的羅傑·潘洛斯曾經建議...
- 喬姆斯基層次結構
存在確定性上下文無關語言不是正則的。存線上性語言不是正則的。存在確定性上下文無關語言不是線性的。存線上性語言不是確定性上下文無關的。線性有界自動機是非確定性圖靈機帶上線性空間的約束。相似的約束在確定性圖靈機上隨之產生了所謂...
- NP複雜度
常用的定義是所謂的“關係定義式”。即對於一個語言L，L在NP中，那么存在多項式時間圖靈機M，和多項式p使得：NP的理解 理解NP有兩個角度：一個角度是作為確定性圖靈機的一個推廣，另一個角度是作為多項式時間可驗證解的算法問題的集合...
- 隨機算法
隨機算法是一個概念圖靈機，也就是在算法中引入隨機因素，即通過隨機數選擇算法的下一步操作。基本概念 一個隨機算法是一種算法，它採用了一定程度的隨機性作為其邏輯的一部分。該算法通常使用均勻隨機位作為輔助輸入來指導自己的行為，...
- 最小費用流問題
若一個算法的計算時間不超過其所求解問題的輸入長度的一個多項式，則稱該算法為多項式時間算法；其中計算時間和輸入長度是以確定性圖靈機為計算模型。通常認為只有多項式時間算法是可以求解大規模的實際問題，故多項式時間算法也稱好算法或者...
- 互動式證明系統
於是我們知道，NP是包含在輪數為1，交換信息長度為多項式的，驗證者是確定性圖靈機的證明體系中的。反過來，這樣的證明體系定義的語言容易看出也是在NP中的。這樣NP就與這樣的證明體系等價。可以證明，當驗證者是確定性圖靈機，每輪交換...
- 單向函式
單向函式 (One-way function)是一種具有下述特點的單射函式：對於每一個輸入，函式值都容易計算（多項式時間），但是給出一個隨機輸入的函式值，算出原始輸入卻比較困難（無法在多項式時間內使用確定性圖靈機計算）。 單向函式是否存在...
- 線性有界自動機
確定型和非確定型圖靈機接受的語言是相同的。非確定型線性有界自動機（以 NDLBA 表示）接受的語言類正好是上下文有關語言。確定型線性有界自動機（以DLBA 表示）的功能不會超過 NDLBA 的，以不等式表示為 其中 L 表示該類自動機接受...
