遞歸可列舉集合 (Recursive enumerable set)

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

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.

Facebook

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