作者dharma (达)
看板Programming
标题[问题] 决定性(判定)问题的三种说法
时间Tue Jul 29 08:39:32 2014
如果没理解错误
决定性问题 = 判定问题
查英文是一样的
下面有三个出处的诠释
它们真的是指相同的事情嘛？
thank
1.维基：
在可计算性理论与计算复杂性理论中，所谓的决定性问题(Decision problem)是一个在某
些形式系统回答是或否的问题。例如：「给两个数字x与y，x是否可以整除y？」便是决定
性问题，此问题可回答是或否，且依据其x与y的值。
2.某书：(忘了哪本抄录下来的)
p193 「判定问题」就是想找出一个严谨的逐步程序，藉由演绎逻辑的形式言自动做出证
明
3.好像是网路看到的：
不可判定问题是更加困难的
例如停机问题
它们无法在任何给定时间内解决
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.163.106.192
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Programming/M.1406594375.A.6AA.html
1F：推 longlongint:某书是什麽书？ 当然是看该领域自己 114.37.232.212 07/31 13:15
2F：→ longlongint:给的定义呀 114.37.232.212 07/31 13:15
3F：推 longlongint:一般Decision翻译成"决策" 1.161.123.30 07/31 13:16
4F：→ longlongint:deterministic翻译成确定性(的) 1.161.123.30 07/31 13:17
5F：→ longlongint:原PO的1应该来自於 人工智慧领域 1.161.123.30 07/31 13:18
6F：→ longlongint:2是应该是从 哲学或逻辑学 来的 1.161.123.30 07/31 13:18
7F：→ longlongint:要不然又是AI里面的自动理论推导机 1.161.123.30 07/31 13:19
8F：→ longlongint:3是演算法或计算机理论的问题 1.161.123.30 07/31 13:20
9F：→ longlongint:更正 计算理论 1.161.123.30 07/31 13:20
10F：→ longlongint:恩... 查了一下WIKI发现自己记忆力不 1.161.123.30 07/31 13:21
11F：→ longlongint:好 楼主抱歉 1.161.123.30 07/31 13:22
13F：→ longlongint:不专业的说法 "可决定"的意思为 1.161.123.30 07/31 13:34
14F：→ longlongint:"可以算出答案、可计算、可以回答" 1.161.123.30 07/31 13:34
15F：→ longlongint:反之则是"不可计算、算不出答案、不 1.161.123.30 07/31 13:34
16F：→ longlongint:能回答" 1.161.123.30 07/31 13:35
17F：→ longlongint:我自己搞错的deterministic则是 1.161.123.30 07/31 13:36
18F：→ longlongint:类似"每一步都明确地知道该如何行动" 1.161.123.30 07/31 13:36
19F：→ Killercat:不可决定的意思其实是... 59.124.251.135 07/31 13:42
20F：→ Killercat:无法确定能再给定时间内得到答案 :P 59.124.251.135 07/31 13:42
21F：→ Killercat:除非有数学证明任意解都有最短循环 59.124.251.135 07/31 13:44
22F：→ Killercat:比方说有名的3n+1问题 59.124.251.135 07/31 13:44