導論篇計算理論簡介計算理論的歷史可計算性可計算性簡介圖靈機不可計算問題遞歸可枚舉不完備定理複雜度複雜度簡介複雜度理論NP-Complete隨機複雜度密碼學理論趨近演算法訊息相關網站參考文獻最新修改簡體版English |
Well-foundedN*N : (0,0) < (0,1) < (0,2) …< (1,0) < (1,1) < …< (2,0) < … 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. 遞歸可列舉集合 (Recursive enumerable set)S is recursive enumerable iff it is either empty or it is the image of a total and 定點理論 (Fixed Point Theorem) (Kleene)Let t be any total computable function. Then it is always possible to find an integer 決定集合論 (Decision Set Theorem) (Rice)Let F be any set of computable functions. The set S = {x | function(x) in set F } |
遞歸可列舉集合 (Recursive enumerable set)
page revision: 1, last edited: 18 Sep 2010 09:06
Post preview:
Close preview