※ 引述《dharma (达)》之铭言： : 如果没理解错误 : 决定性问题 = 判定问题 : 查英文是一样的 No, 你把一些事情混在一起了 你前面说的决定性问题,判定问题我猜是 decision problem 但是你後面的东西是在问 decidable problem ( "可判定性" ) : 下面有三个出处的诠释 : 它们真的是指相同的事情嘛？ : thank : 1.维基： : 在可计算性理论与计算复杂性理论中，所谓的决定性问题(Decision problem)是一个在某 : 些形式系统回答是或否的问题。例如：「给两个数字x与y，x是否可以整除y？」便是决定 : 性问题，此问题可回答是或否，且依据其x与y的值。 yes, 这是 decision problem 的定义 : 2.某书：(忘了哪本抄录下来的) : p193 「判定问题」就是想找出一个严谨的逐步程序，藉由演绎逻辑的形式言自动做出证 : 明 这边我看不懂, 个人猜测他是想说 "一个问题是可判定的代表有一个严谨的逐步程序.." （不过我真的看不太懂, 这段理解可能也是全错） : 3.好像是网路看到的： : 不可判定问题是更加困难的 : 例如停机问题 : 它们无法在任何给定时间内解决 (i) "停机问题" 是一个 "判定问题" (decision problem) 他说的是, 任意给你一个程式以及该程式的输入, 请问用这个输入执行该程式, 他是否会在有限时间内终止计算? (ii) "停机问题" 是 "不可判定的" (undecidable) 对於停机问题这个判定问题, 不存在任何能回答停机问题的程式 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.16.142 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1406608614.A.8E2.html 喔!!你说的这个才是对的 ※ 编辑: suhorng (36.229.107.4), 07/29/2014 21:43:56