[其他] 離散一題

看板Math作者 (俊偉)時間3年前 (2020/10/25 16:43), 編輯推噓1(1推 0噓 38→)
留言39則, 3人參與, 3年前最新討論串10/15 (看更多)
題目: 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://www.ptt.cc/bbs/Math/M.1603615392.A.DC5.html
→
10/25 19:30, 3年前 , 1F
(a)你假設了 "要知道F(x)是否等於y 必須先知道F會不
10/25 19:30, 1F
→
10/25 19:32, 3年前 , 2F
會在x停機" 但光看F(x)會不會是y 有時不見得要知道
10/25 19:32, 2F
→
10/25 19:36, 3年前 , 3F
F在x會不會停機 所以P存在不見得會推到"存在決定一
10/25 19:36, 3F
→
10/25 19:37, 3年前 , 4F
個程式是否停機的演算法
10/25 19:37, 4F
推
10/25 19:39, 3年前 , 5F
(a) 還有一個重點是: 程式不是 P, 而是 P(F,x,y)
10/25 19:39, 5F
→
10/25 19:40, 3年前 , 6F
F, x, y 是已知的, 而不是程式的輸入
10/25 19:40, 6F
→
10/25 19:41, 3年前 , 7F
假設這樣的P存在 我們寫這樣一個程式U(F)使得
10/25 19:41, 7F
→
10/25 19:41, 3年前 , 8F
可以比較 (b) 它就只單純說 P 帶兩個參數 F 和 G
10/25 19:41, 8F
→
10/25 19:41, 3年前 , 9F
這就使得 (b) 要針對所有 F, G 都要算出來
10/25 19:41, 9F
→
10/25 19:43, 3年前 , 10F
(i)如果P(F,F,0)=0 則返回0 (ii)如果P(F,F,0)=1 則
10/25 19:43, 10F
→
10/25 19:44, 3年前 , 11F
返回1 那考慮P(U,U,0)就會得到矛盾
10/25 19:44, 11F
→
10/25 19:46, 3年前 , 12F
??? P是程式 F,x,y是輸入沒錯 P(F,x,y)=1 if F(x)=y
10/25 19:46, 12F
→
10/25 19:47, 3年前 , 13F
P(F,x,y)=0 if F(x)≠y
10/25 19:47, 13F
→
10/25 19:50, 3年前 , 14F
(b)你假設了 "要知道F和G停機的集合是否相等 必須先
10/25 19:50, 14F
→
10/25 19:52, 3年前 , 15F
知道F和G各別會停機的集合" 但有時我們還是有可能在
10/25 19:52, 15F
→
10/25 19:53, 3年前 , 16F
不知道所有集合元素的情況下 證明兩個集合相等 所以
10/25 19:53, 16F
→
10/25 19:55, 3年前 , 17F
P存在一樣不見得會推到"存在決定一個程式是否停機的
10/25 19:55, 17F
→
10/25 19:56, 3年前 , 18F
演算法"
10/25 19:56, 18F
→
10/25 19:58, 3年前 , 19F
不過(b)不存在的證明我要再想想
10/25 19:58, 19F
→
10/25 23:11, 3年前 , 20F
Ok (b)中的P的確會推到halting problem 不過如前所
10/25 23:11, 20F
→
10/25 23:13, 3年前 , 21F
述 原PO的implication是推不過去的
10/25 23:13, 21F
→
10/25 23:16, 3年前 , 22F
令T為一個總是輸出0的程式 我們寫一個程式Q(F,x)使
10/25 23:16, 22F
→
10/25 23:19, 3年前 , 23F
打錯 我們寫一個程式Q(F,x,y)使得 (i)如果x=y 則輸
10/25 23:19, 23F
→
10/25 23:20, 3年前 , 24F
出F(x) (ii)如果x≠y 則輸出0
10/25 23:20, 24F
→
10/25 23:25, 3年前 , 25F
那對所有F和x P(T,Q(F,x,*))的輸出值會決定F是否會
10/25 23:25, 25F
→
10/25 23:27, 3年前 , 26F
在x上停機 但halting problem is "undecidable"
10/25 23:27, 26F
→
10/25 23:32, 3年前 , 27F
上面的(a)(b)中的U,Q,T都是概念性的 我不太清楚你計
10/25 23:32, 27F
→
10/25 23:35, 3年前 , 28F
算理論的底子有多深 如果已經有觸及primitive
10/25 23:35, 28F
→
10/25 23:35, 3年前 , 29F
recursive function, computable function和圖靈機
10/25 23:35, 29F
→
10/25 23:37, 3年前 , 30F
之間的關係 則上面的U,Q,T都可以轉成相對應的機器
10/25 23:37, 30F
→
10/25 23:38, 3年前 , 31F
如果計算理論只是過過水的話 上面勉強可以當證明 冏
10/25 23:38, 31F
→
10/26 06:20, 3年前 , 32F
基本上沒有理論的底，教授就把computability當離散
10/26 06:20, 32F
→
10/26 06:20, 3年前 , 33F
的一堂課教
10/26 06:20, 33F
→
10/26 08:20, 3年前 , 34F
囧 好吧 只是如果沒辦法將問題轉成原本理論中該有
10/26 08:20, 34F
→
10/26 08:20, 3年前 , 35F
的形式 那就很難看出為什麼你原來的推論是不太行的
10/26 08:20, 35F
→
10/26 08:20, 3年前 , 36F
冏
10/26 08:20, 36F
→
10/26 08:20, 3年前 , 37F
不過基本上如果你能至少學一門functional programmi
10/26 08:20, 37F
→
10/26 08:20, 3年前 , 38F
ng以及c的話 上面的論證也是可以用程式經驗來感覺
10/26 08:20, 38F
→
10/26 08:20, 3年前 , 39F
的
10/26 08:20, 39F
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VbJgWt5 (Math)
討論串 (同標題文章)
完整討論串 (本文為第 10 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VbJgWt5 (Math)