→ hwanger : (a)你假設了 "要知道F(x)是否等於y 必須先知道F會不 10/25 19:30
→ hwanger : 會在x停機" 但光看F(x)會不會是y 有時不見得要知道 10/25 19:32
→ hwanger : F在x會不會停機 所以P存在不見得會推到"存在決定一 10/25 19:36
→ hwanger : 個程式是否停機的演算法 10/25 19:37
推 LPH66 : (a) 還有一個重點是: 程式不是 P, 而是 P(F,x,y) 10/25 19:39
→ LPH66 : F, x, y 是已知的, 而不是程式的輸入 10/25 19:40
→ hwanger : 假設這樣的P存在 我們寫這樣一個程式U(F)使得 10/25 19:41
→ LPH66 : 可以比較 (b) 它就只單純說 P 帶兩個參數 F 和 G 10/25 19:41
→ LPH66 : 這就使得 (b) 要針對所有 F, G 都要算出來 10/25 19:41
→ hwanger : (i)如果P(F,F,0)=0 則返回0 (ii)如果P(F,F,0)=1 則 10/25 19:43
→ hwanger : 返回1 那考慮P(U,U,0)就會得到矛盾 10/25 19:44
→ hwanger : ??? P是程式 F,x,y是輸入沒錯 P(F,x,y)=1 if F(x)=y 10/25 19:46
→ hwanger : P(F,x,y)=0 if F(x)≠y 10/25 19:47
→ hwanger : (b)你假設了 "要知道F和G停機的集合是否相等 必須先 10/25 19:50
→ hwanger : 知道F和G各別會停機的集合" 但有時我們還是有可能在 10/25 19:52
→ hwanger : 不知道所有集合元素的情況下 證明兩個集合相等 所以 10/25 19:53
→ hwanger : P存在一樣不見得會推到"存在決定一個程式是否停機的 10/25 19:55
→ hwanger : 演算法" 10/25 19:56
→ hwanger : 不過(b)不存在的證明我要再想想 10/25 19:58
→ hwanger : Ok (b)中的P的確會推到halting problem 不過如前所 10/25 23:11
→ hwanger : 述 原PO的implication是推不過去的 10/25 23:13
→ hwanger : 令T為一個總是輸出0的程式 我們寫一個程式Q(F,x)使 10/25 23:16
→ hwanger : 打錯 我們寫一個程式Q(F,x,y)使得 (i)如果x=y 則輸 10/25 23:19
→ hwanger : 出F(x) (ii)如果x≠y 則輸出0 10/25 23:20
→ hwanger : 那對所有F和x P(T,Q(F,x,*))的輸出值會決定F是否會 10/25 23:25
→ hwanger : 在x上停機 但halting problem is "undecidable" 10/25 23:27
→ hwanger : 上面的(a)(b)中的U,Q,T都是概念性的 我不太清楚你計 10/25 23:32
→ hwanger : 算理論的底子有多深 如果已經有觸及primitive 10/25 23:35
→ hwanger : recursive function, computable function和圖靈機 10/25 23:35
→ hwanger : 之間的關係 則上面的U,Q,T都可以轉成相對應的機器 10/25 23:37
→ hwanger : 如果計算理論只是過過水的話 上面勉強可以當證明 冏 10/25 23:38
→ LiquidTLO : 基本上沒有理論的底，教授就把computability當離散 10/26 06:20
→ LiquidTLO : 的一堂課教 10/26 06:20
→ hwanger : 囧 好吧 只是如果沒辦法將問題轉成原本理論中該有 10/26 08:20
→ hwanger : 的形式 那就很難看出為什麼你原來的推論是不太行的 10/26 08:20
→ hwanger : 冏 10/26 08:20
→ hwanger : 不過基本上如果你能至少學一門functional programmi 10/26 08:20
→ hwanger : ng以及c的話 上面的論證也是可以用程式經驗來感覺 10/26 08:20
→ hwanger : 的 10/26 08:20