作者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/cn.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