解释下列名称术语 1．可计算函数 2．可判定性语言 3．通用图灵机 4. 接受计算历史 5．多项式时间归约 6．NP 完全性

### 回答1：

1 可计算函数：指一个特定的函数，它可以使用算法被计算。
2. 可判定性语言：指可以用一种精确的方式来描述的语言，它具有可判定性，即可以用有限的资源来判断它是否是有效的语言表达。
3. 通用图灵机：一种计算模型，它可以模拟任何其他计算机，可以求解任何可计算问题。
4. 接受计算历史：指计算机在解决问题时所使用的记录，包括输入、输出和中间结果。
5. 多项式时间归约：指一种归约算法，它可以在多项式时间内完成归约操作。
6. NP 完全性：指一种NP问题，它的解决需要搜索空间的大小和多项式时间比例相当大。

### 回答2：
1. 可计算函数：可计算函数是指可以被某种计算模型无限多次迭代地计算出结果的函数。在计算理论中，通常使用图灵机或递归函数作为计算模型，可计算函数是对输入进行计算并产生输出的过程。

2. 可判定性语言：可判定性语言是指可以由某种计算模型判定是或否的语言。在计算理论中，通常使用图灵机作为计算模型，可判定性语言是对输入进行判定并给出肯定或否定的结果的过程。

3. 通用图灵机：通用图灵机是指能够模拟任何其他图灵机的图灵机。它是图灵机的一种特殊形式，具有相同的计算能力，能够执行其他图灵机能执行的所有计算任务。

4. 接受计算历史：接受计算历史是指在给定的计算模型中，对于一个计算过程中所有中间状态的记录。它通常用于证明某个问题的可解性，也用于分析计算过程中的时间和空间复杂性。

5. 多项式时间归约：多项式时间归约是指将一个问题转化为另一个问题，使得在多项式时间内可以解决原问题。通过将一个问题转化为另一个已知的、易于解决的问题，可以简化问题的求解过程。

6. NP完全性：NP完全性是指一个问题既属于非确定性多项式时间（NP）的问题集合，又是NP问题中最难解的一类问题。如果一个问题是NP完全问题，那么它可以通过多项式时间归约转化为任何其他NP问题，且已知不存在多项式时间算法能够完全解决该问题。因此，NP完全问题被认为是计算上最困难的问题之一。

### 回答3：
1. 可计算函数：可计算函数指的是能够在有限时间内用计算机程序计算出结果的函数。根据图灵机的定义，可以用图灵机模拟的计算过程都可以被认为是可计算函数。

2. 可判定性语言：可判定性语言是指能够用判定性算法（即能够给出“是”或“否”答案的算法）判断其输入是否属于该语言的一种语言。可判定性语言也被称为“递归语言”。

3. 通用图灵机：通用图灵机是指具备极高灵活性的图灵机，它能够模拟任意其他图灵机的操作。通用图灵机是图灵完备的，也就是说它能够计算出任意可计算函数。

4. 接受计算历史：接受计算历史是指在图灵机计算过程中的一系列状态和转换步骤。接受计算历史描述了图灵机从开始状态到最后状态经历的所有操作步骤和中间状态。

5. 多项式时间归约：多项式时间归约是指将一个问题A多项式时间内转化为了另一个问题B，使得在已经求解问题B的情况下，问题A也能在多项式时间内求解。这种归约关系在理论计算机科学中用于研究问题的复杂度关系。

6. NP完全性：NP完全性是指一类问题的特性，这类问题既属于NP问题的子集，又是NP问题中最难的问题。如果一个问题是NP完全的，那么它的解可以在多项式时间内验证，并且可以在多项式时间内归约到任何其他的NP问题。NP完全性是理论计算机科学中重要的概念，与许多实际应用问题相关。