※ 引述《dharma (达)》之铭言： : 如果没理解错误 : 决定性问题 = 判定问题 : 查英文是一样的 : 下面有三个出处的诠释 : 它们真的是指相同的事情嘛？ : thank : 1.维基： : 在可计算性理论与计算复杂性理论中，所谓的决定性问题(Decision problem)是一个在某 : 些形式系统回答是或否的问题。例如：「给两个数字x与y，x是否可以整除y？」便是决定 : 性问题，此问题可回答是或否，且依据其x与y的值。 : 2.某书：(忘了哪本抄录下来的) : p193 「判定问题」就是想找出一个严谨的逐步程序，藉由演绎逻辑的形式言自动做出证 : 明 : 3.好像是网路看到的： : 不可判定问题是更加困难的 : 例如停机问题 : 它们无法在任何给定时间内解决 你问的应该是计算理论方面的 turing-decidible 的问题吧 首先要wiki一下turing machine的定义 然後会知道turing machine执行最後会发生3个状态 1.accept 2.reject 3.loop 因此可以把问题的难度分类 turing-decidible的问题是指 存在一turing machine 使其input是答案的就accept 不是答案的就reject 不管怎样不会loop 举个例子 问题为 检查input是否是n个0与n个1的字串 000111 ac, 0000011111 ac, 0101 reject ... 我们可以设计一turing mechine确实可以检查出这件事 而且不管input是什麽都不会掉进loop (建造这个 并不是太简单 也不是太难 通常计算理论课会放在习题 或是老师以此当范例说明) 所以这个问题就是turing-decidible 但有些问题是turing-undecidible 也就是不存在turing mechine 符合 "input是答案的就accept 不是答案的就reject 不管怎样不会loop" 这条件 像停机问题就是turing-undecidible ---------------------------------------------------------- 有个有趣的问题是 电脑上可否写个程式 来 判断任何程式 会停止或掉进无穷回圈 这在一些书上或资料上 都只说因为停机问题是undecidible 所以不可能 这其实是不严谨的 应该更仔细思考 Turing-machine是一种抽象电脑 它的tape可以放进任意大的input 可以比宇宙中所有粒子数还大 而且state数量也没限制 我们一般看到的停机问题的证明都是在此模型上证明的 但真实的电脑不是 它的tape是"有限的" state也是"有限的" 若问可解决的问题 turing-machine比真实的电脑威力还大 所以以真实的电脑为模型的停机问题应该要另外证明 这部份我就没再深入研究了 一般书上或网路上直接那样写其实是逻辑上的错误 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.137.10.127 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Programming/M.1407046172.A.F6C.html ※ 编辑: Arton0306 (220.137.10.127), 08/03/2014 14:42:14 你是指有限tape的turing machine因为configuration有限 所以这model下的停机问题是decidable吗?? 我後来也有想到这是turing-decidable 只是要在无限tape版的去检查有限tape版的 如果是在有限tape(长度n)的去检查有限tape(长度n) 这应该不行 在tape长度短时连另一台machine的encode都放不下XD 状态数我的意思跟你是一样的 有点难表达XD 就|Q|没有上限 ※ 编辑: Arton0306 (220.137.10.127), 08/03/2014 17:39:02 ※ 编辑: Arton0306 (220.137.10.127), 08/03/2014 17:53:16