※ 引述《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