ychael

刘未鹏的数学基础真好，看了他的那篇永恒的金色对角线 ，很简明。
Y Combinator

Y(F) = F(Y(F))



--------------------------------------------------------------------------------

不动点构造
let power_gen = lambda self. P(self(self))

铸造Y Combinator

let Y = lambda F.
let f_gen = lambda self. F(self(self))
return f_gen(f_gen)

哥德尔不完备定理的核心构造式
N(n) is unprovable in T
UnPr(X)来表达“X is unprovable in T”
UnPr( N(n) )
G(n): UnPr( N(n) )，以G的编码g代入公式，得出命题
G(g): UnPr( G(g) ) ‘我是不可在T内证明的

从哥德尔公式到Y Combinator
G(n): UnPr( N(n) )
G(n): P( N(n) )
G(g): P( G(g) )
我们从哥德尔的证明里面直接看到了Y Combinator

(The Halting Problem)
bool God_algo(char* program, char* input)
{
if(<program> halts on <input>)
return true;
return false;
}
bool Satan_algo(char* program)
{
if( God_algo(program, program) ){
while(1); // loop forever!
return false; // can never get here!
}
else
return true;
}

Satan_algo(Satan_algo);