计算理论
数学领域
计算理论(英語:Theory of computation)是數學的一個領域,和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题:
這三方面的問題可以用一個問題來總括:「電腦的基礎能力及限制到什麼程度?」[1]
計算理論的「計算」並非指純粹的算術運算(Calculation),而是指從已知的輸入透過算法來取得一個問題的答案(Computation),因此,計算理論屬於理論計算機科學和應用數學。
為了對計算進行嚴謹的研究,電腦科學家會將計算以數學的方式抽象化,稱為计算模型。有幾種目前在使用的计算模型,其中最出名的是圖靈機[2]。電腦科學家研究圖靈機的原因是它很容易敘述,可以分析,用來證明結果,而且用此模式呈現了許多強而有力的計算模型(參照邱奇-图灵论题)[3]。圖靈機有潛在的,數量無限的記憶能力,這似乎是不可能達到的,不過所有圖靈機解決的可判定性問題[4]都只需要有限量的記憶能力。因此理論上,任何可以用圖靈機解決的(可判定性)問題都只需要有限量的記憶能力。
歷史编辑
計算理論早在所有計算機發明之前便開始了,當時是使用数理逻辑,在20世紀此理論和數學分離,成為一個獨立的學科。
计算理论早期的重要貢獻者有阿隆佐·邱奇、库尔特·哥德尔、艾伦·图灵、斯蒂芬·科尔·克莱尼、约翰·冯·诺伊曼及克劳德·香农等。
參考資料编辑
- ^ Michael Sipser. Introduction to the Theory of Computation 3rd. Cengage Learning. 2013. ISBN 978-1-133-18779-0.
central areas of the theory of computation: automata, computability, and complexity. (Page 1)
- ^ Andrew Hodges. Alan Turing: The Enigma (THE CENTENARY EDITION). Princeton University Press. 2012. ISBN 978-0-691-15564-7.
- ^ Rabin, Michael O. Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. June 2012 [2017-01-17]. (原始内容存档于2019-06-05).
- ^ Donald Monk. Mathematical Logic. Springer-Verlag. 1976. ISBN 9780387901701.
參見编辑
外部連結编辑
- Theory of Computation(页面存档备份,存于互联网档案馆) at MIT
- Theory of Computation(页面存档备份,存于互联网档案馆) at Harvard
- Computability Logic - A theory of interactive computation. The main web source on this subject.
🔥 Top keywords: Baike: 首页淚之女王Special:搜索不夠善良的我們2024年湯姆斯盃金智媛2024年優霸盃金秀賢 (男演員)春色寄情人破墓怪獸8號乘風2024城市猎人排球少年!!背着善宰跑习近平承欢记張敬軒排球少年!!角色列表九龍城寨之圍城逆天奇案2BABYMONSTER六四事件ILLIT許瑋甯李主儐末日愚者與鳳行朴成焄鈴木亮平BOYNEXTDOOR方皓玟周處除三害 (電影)馬陸李美淑Seventeen (組合)崔永元完全省錢戀愛手冊921大地震机动战士GUNDAM SEED FREEDOM第二十条搜查班長1958NewJeans迷宮飯中華民國中华人民共和国林依晨愛的迫降葬送的芙莉蓮幕府將軍 (2024年電視劇)田馥甄三体 (小说)Energy (組合)(G)I-DLE傅崐萁周雨彤Believe-為你架起的橋樑-無職轉生~到了異世界就拿出真本事~Hide (电视剧)劉偉健劍星日本特技玩家徐譽庭郭東延黃道十二宮寄生獸:灰色部隊賀軍翔2024年花蓮地震支配物种朴智恩 (編劇)半生緣 (電影)HYBE邊佑錫WIND BREAKER—防風少年—柯震東香港來自星星的你宁安如梦鄭靚歆尹普美毛泽东白鹿 (演員)無職轉生~到了異世界就拿出真本事~角色列表戀愛兄妹草榴社区我獨自升級安東尼·布林肯李现LE SSERAFIM金秀賢影視作品列表少年歌行臧芮軒三流之路满城尽带黄金甲金正蘭但願人長久 (電影)国际劳动节P站