免費電子書：計算理論

導論篇 計算理論簡介 計算理論的歷史 可計算性 可計算性簡介 圖靈機 不可計算問題 遞歸可枚舉 不完備定理 複雜度 複雜度簡介 複雜度理論 NP-Complete 隨機複雜度 密碼學理論 趨近演算法 訊息 相關網站 參考文獻 最新修改 簡體版 English

文章 皮諾公設系統 Axiom of Natural Number System (Peano) PE1 : 0 exist PE2 : x' = x+1 PE3 : x' > x PE4 : If x' = y' then x = y PE5 : Principle of mathmatical Induction : If P(0) and P(x) -> P(x') then For all x, P(x) 哥德爾不完備定理 Incomplete Theorem (Godel) Sound : every theorem is a logically valid well form formula. Consistent : no well form formula V such that { |-V } and { |- not V }. Complete : every logically valid well form formula is a theorem. Incomplete Theorem : Natural Number System is consistent but incomplete, that is, there is a closed well form formula V such that neither { |- V } nor { |- not V } 圖靈-邱奇假說 Turing Machine Powerful Thesis (Church) 1. There is no formalism to model any mechanical calculus that is more powerful than Turing Machine and equivalent formalisms. 2. Any algorithm can be coded in term of a Turing Machine. 停止問題 Halting Problem is an undecidable problem h(x, y) = if fy(x) <> undefine then 1 else 0 -—(1) suppose that h is computable then we may define function g such that g(x) = if h(x, x) = 0 then 1 else undefine g is also computable , ie g = fp for some integer p then if fp(p) = g(p) = undefine = h(p, p) = if fp(p) <> undefine then 1 else 0, will return 0, contradiction. if fp(p) = g(p) <> undefine = h(p, p) = if fp(p) <> undefine then 1 else 0, will return 1, contradiction 特徵函數 Characteristic function Cs(x) = if x in set S then 1 else 0 遞歸集合 Recursive set S is recursive set iff its characteristic function is computable. It means that there exist a turing maching that compute Cs(x) = if x in set S then 1 else 0 遞歸可列舉集合 Recursive enumerable set S is recursive enumerable iff it is either empty or it is the image of a total and computable function g. S = Ig = {x | x = g(y), y in set N } It means that there exist a turing maching that compute Cs(x) = if x in set S then 1 else (go on forever) 定點理論 Fixed Point Theorem (Kleene) Let t be any total computable function. Then it is always possible to find an integer p such that function(p) = function(t(p)). 決定集合論 Decision Set Theorem (Rice) Let F be any set of computable functions. The set S = {x | function(x) in set F } is recursive iff F = empty of F is the set of all computable functions. 轉化 Reduction A is reducable to B iff there exists a total computable function t such that for any x, in set A iff t(x) in set B NP 完備定理 NP-complete Theorem (Cook) The problem of stating the satisfiability of propositional formulas in conjunctive normal form is NP-complete. Facebook 留言 Facebook Wikidot Post preview: Close preview or Sign in as Wikidot user (will not be published) - + Help: wiki text quick reference 授權 本網頁的作者、授權與引用方式 作者 陳鍾誠，於金門大學資訊工程系，電子郵件：wt.ude.uqn|ccc#wt.ude.uqn|ccc，網站：http://ccckmit.wikidot.com。 授權 本文採用創作共用 (Creative Common) 3.0 版的 姓名標示─非商業性─相同方式分享 授權條款，歡迎轉載或修改使用，但若做為商業使用時必須取得授權，引用本文時請參考下列格式。 中文版 (APA格式) 陳鍾誠 (21 Aug 2010 12:40)，(網頁標題) 免費電子書：計算理論，(網站標題) 陳鍾誠的網站，取自 http://ccckmit.wikidot.com/ct:main ，網頁修改第 1 版。 英文版 (APA格式) Chung-Chen Chen (21 Aug 2010 12:40), Retrieved from http://ccckmit.wikidot.com/ct:main , Page Revision 1.