为什么总体功能无法枚举？

Question

我们了解了职能枚举的概念。实际上，它们对应于编程语言。

在一句话中，教授提到所有总体功能的类（即，每个输入始终终止的功能）是 不是 枚举。这意味着我们无法设计一种编程语言，该语言使我们能够编写所有总体功能，但没有其他功能 - 这真是太好了！

那么，如果我们想要体面的计算能力，我们（显然）（显然）如何接受非终止的潜力呢？

Answer 1

由于对角。如果$（f_e：e in mathbb {n}）$是从$ mathbb {n} $到$ mathbb {n} $的所有总计可计算函数的可计算枚举，这样每一个$ f_e $都是总的，那么$ g（i）= f_i（i）+ 1 $也将是一个总计可计算函数，但它不会在枚举中。那将与序列的假设相矛盾。因此，不可计算的函数枚举可以完全由可计算函数组成。

假设我们想到一个通用可计算函数$ h（e，i）$，其中“通用”表示$ h $是可计算的二进制函数，对于每个可计算的一单位函数$ f（n）$，都有一些$ e $因此，所有$ i $ $ f（i）= h（e，i）$。然后，还必须有一些$ e $，以便$ g（n）= h（e，n）$不是总功能，因为上一段。否则，$ h $将提供可计算的可计算一般函数的可计算枚举，其中包括所有可计算的一单位函数。

因此，每个函数都是函数系统的要求，与该系统中通用函数的存在不相容。对于某些弱系统，例如原始递归函数，每个功能都是总的，但没有通用功能。具有通用函数的更强系统，例如图灵的可计算性，必须具有部分功能，以使通用函数存在。

Answer 2

只是要明确，我们需要区分数学功能（我将其称为 功能 而且通常有许多无数，所以它们根本无法枚举），您可以写的功能：我会称呼它们 程式 或也是 可计算功能.

可数集$ e $的子集$ s $称为 可计算 如果有一个程序，则给定一个元素$ x $ of $ e $的$ x $如果$x∈S$和“否”如果$ x not∈S$响应“是”。 （而且他总是必须回应某件事）一套被称为 递归枚举 如果该程序被授权不回应而不是说“否”。 （相当于要求该程序必须按任何顺序打印所有$ s $的元素）

所有程序的集合 有限套件 是 枚举 因为您可以编写一个解释器，该解释器只需在有限集的所有元素上运行程序，然后返回“是”，如果它们都终止。 （但看不到他们中的任何一个都没有）

您的教授说，所有计划的集合 无限集 是 无法枚举 因为您不能仅仅在无限数量的元素上运行程序。

但这并不意味着这是不好的：

1. 例如，如果所有程序都是 可证明 总数是 枚举 因为您可以列举所有证明，并机械检查它们是否证明您的程序是总的。

2. 即使是枚举的套装也不是实用的，因为您可能必须永远等待，而不必确定该程序是否会终止一天。我看不到如何使用列举所有总功能的程序...

在某些编程语言中，您编写的所有内容都可以通过静态键入终止！甚至有些人可以保证您多项式界限。他们目前大多是学术性的，写在这些文章中可能会让您感觉到在Python写作的限制更大，但是有很多研究人员正在研究这一点。

因此，回答您的问题：从某种意义上说，是的。潜在的非终止是必不可少的（目前是最高的计算能力）。但是，我发现这与总体功能是否列举的事实直接相关。您仍然可以编写所有总程序！