- 主题:囚徒猜钥匙问题
这是有限集啊，不存在非构造性的吧。
【 在 GGGGDDDDK 的大作中提到: 】
: 是没啥用呀，只要这个策略有非零概率不能成功找到就不是有效的
: 而且问题是——对有些题目来说，“策略有漏洞”的理由是非构造性的
: 所以我认为那句话可能反倒多余了——
: ...................
--
FROM 76.126.252.*
你这一本正经的……
【 在 zyf674 的大作中提到: 】
: 钥匙的位置是64种可能性，entropy是log2(64) = 6 bit，你翻一面的信息量是1bit，只能判断1bit的位置信息，比如钥匙是在上半棋盘还是下半棋盘，所以至少需要允许翻6个硬币才行
--
FROM 76.126.252.*
问题是这个可以构造啊。
任何关于有限集的问题，你能给出非构造性的证明（证明该命题确实是正确的），那么你就一定可以给出构造性的证明。
【 在 GGGGDDDDK 的大作中提到: 】
: 并不是只有选择公理那种算非构造性
: 例如经典的问题，从1到n里轮流取一个数，不能取已取的数的约数，
: 无法取者输
: ...................
--
FROM 76.126.252.*
只要知道构造性证明存在就行了。
【 在 GGGGDDDDK 的大作中提到: 】
: 非构造性证明 O(1)
: 构造性证明 O(n^k)
:
--
FROM 76.126.252.*
“所有正整数”这是无限问题。
这个楼里讨论的没有无限。
无限不存在。
【 在 GGGGDDDDK 的大作中提到: 】
: 可能无法用有限个字概括对所有正整数n的必胜策略
:
--
FROM 76.126.252.*
因为此处我们定义的“算法”是要对“任意n”成立。所以这个算法成了一个要处理无限的存在。
如果我们给出最大限制n < N，则总能找到算法。
【 在 GGGGDDDDK 的大作中提到: 】
: 但是确实没有有效算法能够给出对某个指定正整数n的必胜策略呀
: 又例如这个例子：
: 对正整数n，定义f(n)为保持n的数字顺序不变的前提下，在任意位置添加若干个数字，
: ...................
--
FROM 76.126.252.*
我对“有效算法”的理解是"effective procedure"，如同希尔伯特的“可决定问题”所说的。
或者说，是否是图灵机可计算的。
【 在 GGGGDDDDK 的大作中提到: 】
: 可能你我的想法区别是，我认为暴力枚举不算有效算法？
:
:
--
FROM 76.126.252.*