免費電子書:計算理論

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License