基本介紹
- 中文名:通用圖靈機
- 外文名:Universal Turing Machine
- 意思:能夠模擬其它所有圖靈機的圖靈機
- 簡稱:UTM
通用圖靈機(universal Turing machine,又稱Machine U)是一種圖靈機,由艾倫·圖靈在1936年發明。這種多用途單機器(計算機器)模型可以“運行”任何任意(但well-formed...
圖靈機 (Turing machine, TM) 是由圖靈在1936年提出的,它是一種精確的通用計算機模型,能模擬實際計算機的所有計算行為。所謂的圖靈機就是指一個抽象的機器,它有...
英國數學家A.M.圖靈提出的一種抽象計算模型,用來精確定義可計算函式。圖靈機由一個控制器、一條可無限延伸的帶子和一個在帶子上左右移動的讀寫頭組成。這種機器...
Post-圖靈機是一種特別簡單類型的圖靈機的"程式公式化",由下面描述的Emil Post的圖靈等價的計算模型構成。(Post的模型和圖靈的模型,儘管相互之間非常類似,但卻是...
圖靈完全是指在可計算性理論中,程式語言或任意其他邏輯系統等可以用於通用圖靈機的計算能力。換言之,此系統可與通用圖靈機互相模擬。雖然實際機器會受到存儲能力的...
圖靈完全指在可計算性理論中,程式語言或任意其他的邏輯系統如具有等用於通用圖靈機的計算能力。換言之,此系統可與通用圖靈機互相模擬。這個詞源於引入圖靈機概念的...
與此同時,圖靈還提出了通用圖靈機的概念,它相當於通用計算機的解釋程式,這一點直接促進了後來通用計算機的設計和研製工作,圖靈自己也參加了這一工作。...
如果一個計算系統可以計算每一個圖靈可計算函式,那么這個系統就是圖靈完備的;或者說,這個系統可以模擬通用圖靈機。 [4] 圖靈完備性也可以用來描述計算機語言的計算...
線性有界自動機;用來描述通用計算機計算能力的圖靈機模型;進行與轉移函式,轉移狀態有關輸出的時序機;由一些基本語句構成程式框圖的波斯特機;隨機存儲機;堆疊自動機;...
量子計算是一種遵循量子力學規律調控量子信息單元進行計算的新型計算模式。對照於傳統的通用計算機,其理論模型是通用圖靈機;通用的量子計算機,其理論模型是用量子力學...
在數理邏輯和理論計算機科學中,暫存器機是以類似於使用圖靈機的方式使用的一類抽象機。所有模型都是圖靈等價的。暫存器機得名於它有一個或多個“暫存器” -- 替代...
在60年代初已構造出一個7狀態4字母單帶通用圖靈機;在二維帶圖靈機的範圍內,還可改進到2狀態2字母。無限自動機論識別器 編輯 圖靈機等一般自動機所識別的集恰...
人造肌肉計算機是紐西蘭奧克蘭大學科學家班傑明·馬克·奧布賴恩設計出的,其採用最簡單的通用圖靈機設計,只要時間和記憶體足夠,就能解決任何計算問題,並且也能“思考”。...
從無限制文法和圖靈機的等價性上,給定一個字元串 是否屬於某個無限制文法的語言的決定性問題一般是不可判定的。給出一個語言的描述完全可能建立一個通用無限制...
作為最早期的通用電子計算機,Pilot ACE於1950年5月運行了第一個程式。當時,它是世界上運行速度最快的計算機。該款計算機是計算機先驅阿蘭·圖靈(Alan Turing)所研製...
量子計算機可等效為量子圖靈機,量子圖靈機可等價為量子邏輯電路,因此可通過量子邏輯門的級聯構建量子計算機.目前常用的量子邏輯門有NOT門、CNOT門、Toffoli門、通用...
一些人工智慧數據結構(比如語義網)還是很普通的,使得它們可以為幾乎所有能夠描述出的東西建模,或者正像通用圖靈機一樣,使得它們可以為任意的可計算函式建模。因此,一...
圖靈也以算法概念為通用計算機(純理論器件)作出定義,後來稱為圖靈機,取代哥德爾漸趨累贅的通用語言。除了記憶體限制,現代電腦已經具備圖靈完全的條件,也就是說,現代電腦...
求解的需要討論正則語言、上下文無關語言的文法、識別模型及其性質、圖靈機的基本...9.2.4多維圖靈機2539.2.5其他圖靈機2559.3通用圖靈機2579.4幾個相關的概念259...
在這篇文章里胡世華回顧了通用電子計算機的歷史,指出正是J.馮·諾依曼(von Neumann)受了A.M.圖靈(Turing)定義的通用圖靈機的啟示而設計了第一架通用電子計算機...
《形式語言與自動機理論(第2版)》(主教材)一書的配套教學輔導用書,按照主教材...9.2.4 多維圖靈機9.2.5 其他圖靈機9.3 通用圖靈機9.4 幾個相關的概念...
《計算機科學的數學基礎》共分形式語言與自動機理論,可計算理論,邏輯學,程式設計...9.2 通用圖靈機和一個不可判定問題9.3 RICE定理和某些其他的不可判定問題...
本書作為《形式語言與自動機理論(第3版)》(主教材)的配套教學輔導用書,按照主...9.2.4多維圖靈機1659.2.5其他圖靈機1669.3通用圖靈機1689.4幾個相關的概念170...
早在30年代,圖靈對存在通用圖靈機的邏輯證明表明,製造出能編程式來作出任何計算的通用計算機是可能的,這影響了40年代出現的存儲程式的計算機(即馮諾依曼型計算機)的...
2.3可計算性2.3.1圖靈機2.3.2通用圖靈機2.3.3Church論題2.3.4暫存器機2.3.5細胞自動機2.4形式語言2.4.1文法與語言2.4.2喬姆斯基體系...
通用圖靈機影響了計算機的設計思想。計算理論主要包括算法、算法學、計算複雜性理論、可計算性理論、自動機理論和形式語言理論等。作為計算機科學的理論基礎的計算理論...