可解 可判定 可计算 规约

问:问题的分类:

答:分为两种，一种是判定问题，一种是优化问题，其中优化问题可以转换为判定问题．

问题:如何表示问题?

答:（1）问题和程序（算法），形式和答案五花八门；

（2）一个程序可以编码成有限长字符串；

（3）一个输入可以编码成有限长字符串；

（4）程序的回答?简化为只有是和否；

（5）计算理论中的问题:

具有某种性质的有限字符串的集合；

（6）一个程序只能对应一个问题（字符串集合）。

问题:每个问题都有对应程序吗?

答:一个程序（算法）是一个有限长的字符串，一个语言（问题）是一些有限长字符串的集合，一个程序只能对应一个语言。

计算机模型

什么是现代计算机模型?

答:

现代计算机模型计算机有各种不同的模型。现代计算机模型定义了计算机内部的结构，主要可归纳为以下三点:

（1）计算机有5个组成部分，分别是输人、存储、处理（运算）、控制和输出。

（2）计算机的程序和程序运行所需要的数据以二进制形式存放在计算机的存储器中。

（3）计算机根据程序的指令序列执行，即程序存储的概念。

问:什么是计算能力?

答:所谓计算能力，就是指数学上的归纳和转化的能力，即把抽象的、复杂的数学表达式或数字通过数学方法转换为我们可以理解的数学式子的能力。

问:图灵机模型与什么的计算能力是等价的?

答:莱姆德演算，马尔可夫算法，递归函数。

计算理论

问:经典计算理论研究的内容是什么?

答:计算的模型（自动机理论）

计算的能力（可计算性理论）

计算的复杂性

问题:计算理论?

回答:计算理论是用来研究计算的过程与功效的数学理论。1936年，数理逻辑专家便提出了计算模型的问题，借以解决每个问题是否都有解。通用图灵机影响了计算机的设计思想。计算理论主要包括算法、算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言理论等。作为计算机科学的理论基础的计算理论已经广泛应用于科学的各个领域，程序存储式计算模型就是以图灵机为基础产生的，程序设计中则使用了递归函数的思想，自动机作为一种基本工具被广泛的应用在程序设计的编译过程中。随着科技的发展，计算理论会更多的应用于其他领域。

问题:计算理论由什么组成?

答:可计算性，计算复杂性，计算模型。

问题:算法与计算的关系?

答:计算是一种将单一或复数之输入值转换为单一或复数之结果的一种思考过程。算法指的是一种计算过程或—问题的求解过程。两者的关系为:问题的求解是计算，求解算法中的每个步骤是计算；计算的过程是算法，算法又由计算步骤构成；计算的目的由算法实现，算法的执行由计算完成。

问:计算理论研究的主要问题是?

答:可计算性，计算复杂性和计算模型。

问:计算理论的核心问题是什么?

答:计算模型及其计算能力；

问题是否可解——可计算性；

问题是否难解——计算复杂性。

问题:不可解问题是指什么?

答:指的是这类问题无论怎样都不可能有一个正确的算法可以解决。

存在图灵机解决不了的问题吗?

答:存在，这类问题称为不可判定问题。

问:存在程序做不到的事情，也就是说也有图灵机做不到的事情吗?叫什么?

答:存在，叫不可判定问题。

可计算

计算的定义是什么?

一个通过有限次运算就可以决定的过程。

问题:可计算性理论的基础是什么?

答:是图灵论题，即凡是可计算的函数，都可以用图灵机计算。

图灵对可计算的定义?

答:（1）被求解问题需要形式化；

（2）必须设计一个算法；

（3）算法需要有合理的复杂度（空间与时间复杂度）

问题:什么是可计算性?

答:可计算性是指一个实际问题是否可以使用计算机来解决，事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”。

问题:图灵可计算性是在哪里提出的?

答:1936年，图灵在他的著名论文《论可计算数在判定问题中的应用》中定义了计算、计算机器和通用机器，并且指出停机问题是不可计算的。

问题:任何问题都能编程解决吗?

答:不是，图灵机不可判定问题，NP完全问题等，只要是不可计算的问题，一个不能被任何有步骤的、确定性的算法所能解决的问题那都是不行的，因为无法抽象出计算模型，因此也无法编写成程序。

可解

问题:什么样的问题是可解的问题?

答案:在有限时间内可计算出来的问题。

问题:问题的可解性依赖于计算机的快慢吗?

答案:问题的可解性不依赖于计算机的快慢。一个问题在有限的时间内可以把它求解出来，则该问题是可解的，计算机的快慢并不能改变它这一性质，只是问题求解出来时间的长短不一样，但总是能在有限的时间内求解出来。

问题:如何判断一个问题是否不可解?

回答:如果一个问题在图灵机上不可解，那么该问题便是不可解问题。

请列举三个不可解问题:

（1）图灵不停机问题

（2）三十六军官问题

（3）七桥问题

什么叫做不可解问题?举例说明?

答:不可解问题（Undecidable Decision Problem）指的是这样一种问题:他无论如何也不可能有一个正确的算法来解决。虽然不可思议，但这种问题被证明确实是存在的。图灵在1936年（那时还没电脑，我们的父亲是在没有设备支持的纯理论基础上提出来的，致敬）提出了第一个不可解问题的实例:The Halting Problem。

The Halting Problem是问，输入一段程序代码和一个针对此程序的输入，能否编程判断运行这个程序后程序是否会终止。

这个问题的答案是否定的。也就是说，不可能有一种算法可以正确判断一个指定的程序运行后，给予指定的输入，程序最后出不出得来。换句话说，The Halting Problem是一个不可解问题。

判定

问题:请举出一个判定性问题的例子，并找出其对应的求解问题。

答:判定性问题:地球是不是圆的?

求解问题:地球是圆的吗?

问题:举一个判定性问题的例子，说出其相对应的求解问题。

答:判定性问题:太阳每天从东边升起从西边落下?

对应的求解问题:太阳每天从哪里升起?又从哪里落下?

问:什么是判定问题?

答:判定问题是数理逻辑中的一个重要问题。它表现为寻求一种能行的方法、一种机械的程序或者算法，从而能够对某类问题中的任何一个在有穷步骤内确定是否具有某一特定的性质。

问:何为判定问题?

答:判定问题是数理逻辑中的一个重要问题，它表现为寻求一种能行的方法，一种机械的程序或算法，从而能够对某类问题中的任何一个在有穷步骤内确定是否具有某一种特定的性质，所有的求解问题都可以转化为判定问题。

1.问题:什么是可判定性问题?

答:是一个在某些形式系统回答是或否的问题。

问:如何理解判定问题?

答:判定问题表现为寻求一种能行的方法、一种机械的程序或者算法，从而能够对某类问题中的任何一个在有穷步骤内确定是否具有某一特定的性质。

如果对某类问题已经获得能行的方法，就说明这类问题是可判定的，或者说其判定问题是可解的；如能够证明某类问题不可能存在一种能行的方法，就说这类问题不是能行可判定的。

从语义方面考虑，判定问题是要确定一公式是否常真，亦即是否普遍有效，或者可否满足；

在语法方面，它是要确定某一公式是可证，还是可否证。

问题:图灵可判定的定义?

如果一个语言能被图灵机判定或识别，则称它是图灵可判定的。

问:什么叫图灵可识别?什么叫图灵可判定?

答:如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。

如果一个语言能被某一图灵机判定，则称它是图灵可判定的。

确定性 非确定性

问:什么是非确定性问题?

答:无法直接计算得到的，只能通过间接的“猜算”来得到结果的问题。

问题:什么是非确定性?什么是确定性?

回答:所谓非确定性是指在理论计算机科学中，针对各种计算机器模型（自动机），在每一时刻，根据当时的状态和输入，若机器有多个动作可供选择时，则称机器为非确定性的；相反，若机器的动作可唯一确定时，称机器为确定性的。

问:什么是非确定性问题?

答:有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢?这样的公式是没有的。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。

问:谈谈你对非确定算法的理解?

答:NP类问题通常比P类问题难，它意味着有限的资源内找不到一个算法能在多项式时间内解决。于是理论上把资源扩充到需要多少有多少，再采用一种办法，用某种技术一步步地猜测，最后检验猜测结果，看是否符合条件的正确解。由于这种办法是猜出来的，因此每次运行过程都存在随机性，并且由于资源数也是不确定的，因此这种办法叫做非确定性算法。这种算法要对猜对的最终结果进行检验，看是否符合，就是判断yes或no的问题，因此非确定算法是决策性问题。

可归约

问题:图灵机的可归约性

答:如果语言A相对于语言B是可判定的，则说语言A，图灵机可归约到语言B。

问:什么是归约?

答:归约旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题。

什么是图灵的可归约性?

答:图灵可归约性，是计算机语言B的一个谕示，是一个能够报告某个串W是否为B的成员的外部装置。语言B的一个谕示是一个能够报告某个串W是否为B的成员的外部装置。一个谕示图灵机是一个修改过的图灵机，它有询问一个谕示的额外能力。

语言A图灵可归约到语言B，如果A相对于B是可判定的A ＜＝T B

问 :归约的作用是什么?

答:归约旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题。