圖靈完備性
編輯在可計算性理論中,如果一個數據操作規則系統(例如計算機的指令集、編程語言或元胞自動機)可以用來模擬任何圖靈,則它被認為是圖靈完備的或計算通用的 機器(由英國數學家和計算機科學家艾倫圖靈設計)。 這意味著該系統能夠識別或決定其他數據操作規則集。 圖靈完備性被用作表達這種數據操作規則集的力量的一種方式。 今天幾乎所有的編程語言都是圖靈完備的。
一個相關的概念是圖靈等價——如果 P 可以模擬 Q 并且 Q 可以模擬 P,則兩臺計算機 P 和 Q 被稱為等價的。Church-Turing 論文推測任何其值可以由算法計算的函數都可以由 圖靈機,因此如果任何現實世界的計算機都可以模擬圖靈機,那么圖靈就等同于圖靈機。 通用圖靈機可用于模擬任何圖靈機,并通過擴展任何可能的現實世界計算機的計算方面。
要表明某個東西是圖靈完備的,只要表明它可以用來模擬某個圖靈完備的系統就足夠了。 沒有物理系統可以擁有無限內存,但如果忽略有限內存的限制,大多數編程語言在其他方面都是圖靈完備的。
非數學用法
編輯在口語中,術語圖靈完備和圖靈等價物用于表示任何現實世界的通用計算機或計算機語言都可以近似模擬任何其他現實世界的通用計算機或計算機語言的計算方面。 在現實生活中,這導致了計算虛擬化和仿真的實用概念。
到目前為止構建的真實計算機可以像單磁帶圖靈機一樣進行功能分析(磁帶對應于它們的內存); 因此,相關的數學可以通過將它們的操作抽象得足夠遠來應用。 然而,真實計算機的物理資源有限,因此它們只是線性有界自動機完備。 相比之下,通用計算機被定義為具有圖靈完備指令集、無限內存和無限可用時間的設備。
正式定義
編輯在可計算性理論中,幾個密切相關的術語用于描述計算系統(例如抽象機或編程語言)的計算能力:
圖靈完備性 可以計算每個圖靈可計算函數的計算系統稱為圖靈完備(或圖靈強大)。 或者,這樣的系統是一個可以模擬通用圖靈機的系統。圖靈等價一個圖靈完備系統被稱為圖靈等價,如果它可以計算的每個函數也是圖靈可計算的; 即,它計算與圖靈機完全相同的函數類別。 或者,圖靈等效系統是可以模擬通用圖靈機并被通用圖靈機模擬的系統。 (所有已知的物理上可實現的圖靈完備系統都是圖靈等價的,這增加了對 Church-Turing 論點的支持。)(計算的)普適性如果一個系統可以計算系統可計算的每個函數,那么它就被稱為關于一類系統的普適系統 在那個類中(或者可以模擬每個系統)。 通常,術語“通用性”默認用于圖靈完備類系統。 術語弱通用有時用于區分系統(例如元胞自動機),其通用性僅通過修改圖靈機的標準定義以包含具有無限多個 1 的輸入流來實現。
歷史
編輯圖靈完備性的重要意義在于,計算設備的每個真實世界設計都可以由通用圖靈機模擬。 Church-Turing 論文指出這是一個數學定律——通用圖靈機原則上可以執行任何其他可編程計算機可以執行的計算。 這并沒有說明編寫程序所需的工作量,也沒有說明機器執行計算可能需要的時間,也沒有說明機器可能擁有的與計算無關的任何能力。
Charles Babbage 的分析引擎(1830 年代)如果在設計時就已建成,那將是xxx臺圖靈完備機器。 巴貝奇贊賞這臺機器能夠進行出色的計算,包括原始邏輯推理,但他并不認為沒有其他機器可以做得更好。 從 1830 年代到 1940 年代,加法器和乘法器等機械計算器被建造和改進,但它們不能執行條件分支,因此不是圖靈完備的。
在 19 世紀后期,利奧波德·克羅內克 (Leopold Kronecker) 闡述了可計算性的概念,定義了原始遞歸函數。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/198191/