# 皮諾公設系統

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,
if fp(p) = g(p) <> undefine = h(p, p) = if fp(p) <> undefine then 1 else 0,

# 特徵函數

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.