计算机导论：令人困惑的问题

2023-11-18 理论教育版权反馈

【摘要】：一般情况下，用户需要等待相当长一段时间以后，才估计现在运行的程序可能陷入了死循环，会强行终止该程序的运行。我们把不具有确定性答案的问题称为不可解问题。我们希望计算机解决的许多问题是不可解的问题。这就像医生诊断某个患者的病因，只能基于“可能”的基础上，不可能百分之百的正确。要说明的是，对于大多数不可解的问题，虽然我们不能百分之百的肯定求解方法正确，但我们能做到在大部分情况下求解方法正确。

每天都有一些程序设计人员编写一些陷入死循环的程序。当一个程序处于死循环状态时，我们无法确切地知道这个程序是一个运行得很慢的程序，还是一个陷入了死循环的程序。一般情况下，用户需要等待相当长一段时间以后，才估计现在运行的程序可能陷入了死循环，会强行终止该程序的运行。如果存在一个算法（或者说一个程序），能预先判断出某个程序会陷入死循环，将简化许多问题的处理方法，这称为停机问题。遗憾的是停机问题是一个没有确定答案的问题。

停机问题有许多不同的表述方法。下面给出停机问题的一个著名例子。

【例6-6】停机问题。当输入任意一个整数时，判断运行下列程序代码段是否会停机。程序代码段为：

WHILE（n＞1）

{

IF（n％2！＝0）THEN n＝3*n＋1；

ELSE n＝n/2；(www.chuimin.cn)

}

其中，算术表达式n％2表示结果为n除以2后的余数，所以分支判断条件n％2！＝0，是判断数值n是否为奇数。算术表达式n/2表示结果为n除以2的整数部分。

分析：这段程序代码对所有输入整数n都会停机吗？没有人知道答案。很多研究者做过的许多试验只能表明：已经试过的每一个输入数值该代码段都会停机。

算法要求具有确定性，但是，许多问题的求解步骤不具有确定性的答案。我们把不具有确定性答案的问题称为不可解问题。

我们希望计算机解决的许多问题是不可解的问题。例如，判断任意一个程序中是否存在计算机病毒的问题是一个有实用意义的问题。所谓计算机病毒，就是怀有恶意的一些人蓄意强加在计算机中的一段“捣乱”程序。但遗憾的是，我们不能肯定地确定任意一个程序是否包含计算机病毒。因此，所有反病毒程序测试出的某个程序包含病毒的诊断，都只能基于“可能”的基础上。这就像医生诊断某个患者的病因，只能基于“可能”的基础上，不可能百分之百的正确。

要说明的是，对于大多数不可解的问题，虽然我们不能百分之百的肯定求解方法正确，但我们能做到在大部分情况下求解方法正确。这就像一个医生在给病人开刀前，虽然没有百分之百的把握能肯定手术成功，但能做到大部分情况下手术成功。

计算机导论：令人困惑的问题

相关推荐