作者LiquidTLO (俊偉)
看板Math
標題[其他] 離散一題
時間Sun Oct 25 16:43:09 2020
題目:
https://imgur.com/a/THhEDA0
不知道想法對不對
解法會不會不嚴謹
(a)
To check whether F halts on input x
-> this is the halting problem
∵Halting problem is unsolvable
∴ P cannot exist
(b)
To find whether F and G halt on the same inputs
-> i. To find F halts on those inputs
ii. To find G halts on those inputs
∵ i & ii are both halting problem
and halting problem is unsolvable
∴ P cannot exist
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.224.180.237 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1603615392.A.DC5.html
1F：→ hwanger : (a)你假設了 "要知道F(x)是否等於y 必須先知道F會不 10/25 19:30
2F：→ hwanger : 會在x停機" 但光看F(x)會不會是y 有時不見得要知道 10/25 19:32
3F：→ hwanger : F在x會不會停機 所以P存在不見得會推到"存在決定一 10/25 19:36
4F：→ hwanger : 個程式是否停機的演算法 10/25 19:37
5F：推 LPH66 : (a) 還有一個重點是: 程式不是 P, 而是 P(F,x,y) 10/25 19:39
6F：→ LPH66 : F, x, y 是已知的, 而不是程式的輸入 10/25 19:40
7F：→ hwanger : 假設這樣的P存在 我們寫這樣一個程式U(F)使得 10/25 19:41
8F：→ LPH66 : 可以比較 (b) 它就只單純說 P 帶兩個參數 F 和 G 10/25 19:41
9F：→ LPH66 : 這就使得 (b) 要針對所有 F, G 都要算出來 10/25 19:41
10F：→ hwanger : (i)如果P(F,F,0)=0 則返回0 (ii)如果P(F,F,0)=1 則 10/25 19:43
11F：→ hwanger : 返回1 那考慮P(U,U,0)就會得到矛盾 10/25 19:44
12F：→ hwanger : ??? P是程式 F,x,y是輸入沒錯 P(F,x,y)=1 if F(x)=y 10/25 19:46
13F：→ hwanger : P(F,x,y)=0 if F(x)≠y 10/25 19:47
14F：→ hwanger : (b)你假設了 "要知道F和G停機的集合是否相等 必須先 10/25 19:50
15F：→ hwanger : 知道F和G各別會停機的集合" 但有時我們還是有可能在 10/25 19:52
16F：→ hwanger : 不知道所有集合元素的情況下 證明兩個集合相等 所以 10/25 19:53
17F：→ hwanger : P存在一樣不見得會推到"存在決定一個程式是否停機的 10/25 19:55
18F：→ hwanger : 演算法" 10/25 19:56
19F：→ hwanger : 不過(b)不存在的證明我要再想想 10/25 19:58
20F：→ hwanger : Ok (b)中的P的確會推到halting problem 不過如前所 10/25 23:11
21F：→ hwanger : 述 原PO的implication是推不過去的 10/25 23:13
22F：→ hwanger : 令T為一個總是輸出0的程式 我們寫一個程式Q(F,x)使 10/25 23:16
23F：→ hwanger : 打錯 我們寫一個程式Q(F,x,y)使得 (i)如果x=y 則輸 10/25 23:19
24F：→ hwanger : 出F(x) (ii)如果x≠y 則輸出0 10/25 23:20
25F：→ hwanger : 那對所有F和x P(T,Q(F,x,*))的輸出值會決定F是否會 10/25 23:25
26F：→ hwanger : 在x上停機 但halting problem is "undecidable" 10/25 23:27
27F：→ hwanger : 上面的(a)(b)中的U,Q,T都是概念性的 我不太清楚你計 10/25 23:32
28F：→ hwanger : 算理論的底子有多深 如果已經有觸及primitive 10/25 23:35
29F：→ hwanger : recursive function, computable function和圖靈機 10/25 23:35
30F：→ hwanger : 之間的關係 則上面的U,Q,T都可以轉成相對應的機器 10/25 23:37
31F：→ hwanger : 如果計算理論只是過過水的話 上面勉強可以當證明 冏 10/25 23:38
32F：→ LiquidTLO : 基本上沒有理論的底，教授就把computability當離散 10/26 06:20
33F：→ LiquidTLO : 的一堂課教 10/26 06:20
34F：→ hwanger : 囧 好吧 只是如果沒辦法將問題轉成原本理論中該有 10/26 08:20
35F：→ hwanger : 的形式 那就很難看出為什麼你原來的推論是不太行的 10/26 08:20
36F：→ hwanger : 冏 10/26 08:20
37F：→ hwanger : 不過基本上如果你能至少學一門functional programmi 10/26 08:20
38F：→ hwanger : ng以及c的話 上面的論證也是可以用程式經驗來感覺 10/26 08:20
39F：→ hwanger : 的 10/26 08:20