# Well-founded

N*N : (0,0) < (0,1) < (0,2) …< (1,0) < (1,1) < …< (2,0) < …
If we use a algorithm to enumerate from (0,0) to (2,0), it may fall into infinite loop.
If we use a algorithm to enumerate from (2,0) to (0,0), it always terminate.

# Mathematical Induction

$f(0),  \forall x \quad f(x) => f(x+1) \forall x \quad f(x)$

# 特徵函數 (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.