language-agnostic - 如何编写所有可计算函数的枚举？

Question

动机：我希望能够在没有一阶函数的语言中使用玩具函数式编程，方法是使用自然数而不是函数。

通用函数是一个函数 f : N -> (N -> N)，相当于 f : N * N -> N 枚举所有可能的可计算函数。换句话说，有一个数字 k 使得 f(k) 是平方函数，有一个数字 j 使得 f(j) 是第 n 个素数函数等。

要编写这样一个函数，可以采用任何图灵完备的语言（编程语言编译器、lambda 演算、图灵机..​​....）并枚举所有程序。我希望不仅允许评估，还允许对加法、合成、柯里化等功能进行操作。例如，给定两个函数 f,g 的索引，我想知道函数 f+g 或由 g 组成的 f 的索引是什么。这将允许“玩具函数式编程”。

编写这样的代码库的好方法是什么？我不是在寻找难以计算 10 阶乘的简约 Turing tarpit，我也不想编写高级编译器。它应该具有一些基本功能，例如添加和编写循环的可能性，但仅此而已。

欢迎使用所有高级语言的解决方案。伪代码、Haskell 和 Python 是首选。您可以假设任意精度算术。eval不允许使用或类似的。

澄清：枚举函数将由所有部分递归（可计算）函数组成- 这包括不会在某些输入上停止的函数。在这种情况下，通用功能将挂起；当然这是不可避免的。另请参阅：m-recursive 函数 - http://en.wikipedia.org/wiki/Μ-recursive_function。

Answer 1

你想要的是一个解释器。

首先，任何具有您想要的属性的枚举都不适合您想要在前 2^32 甚至前 2^64 整数中操作的有趣函数。因此，您将需要更大的整数，分配在内存中的某个位置并通过指针引用。

那么，为什么不在任何现有语法中使用表示程序的字符（字符串）数组呢？如果这让您满意，可以将这样的字符串视为整数。要计算的函数的编号f1()+f2()是由（f1 的表示）、“+”和（f2 的表示）组成的字符串。你明白了……

这种方法没有的是函数表示的唯一性，这可能暗示在您的问题中（我不确定）。我可以肯定的是，表示的唯一性与对函数表示的简单甚至可计算的组合操作是不相容的——例如，如果不是这种情况，就会有一个简单的解决方案来解决停止问题。

Answer 2

While it is not too hard to enumerate all possible expressions in some language, you won't be able to restrict these to those expressions that denote terminating functions.

But if you are not interested in termination, using combinators (with some arithmetic primitives thrown in for usefulness) might be the best way, since you avoid introducing variable names that way.

Answer 3

正如 Pascal 所说，您想要的是解释器，但可以做得更好：直接将处理器用作解释器。

将数字 N （例如，作为一些大的 int 数组）直接提供给缓冲区并将此缓冲区作为机器代码执行。

对于您的计算机能够执行的每个可能的功能，都存在一个 N。不幸的是。并非每个 N 都是有效程序（没有要求）或终止程序（这是不可能的）。

另一方面，该功能将生成魔兽世界、Microsoft Office 17（包括 Service Pack 6）和 Windows 9 等宝石。

Answer 4

这不是一个简单的问题。我想你必须从一个能够一个一个生成所有函数的函数生成器开始。这将导致枚举。

既然你必须处理多个无尽的维度......让我们考虑一下。

让我们将问题简化为具有 n 个参数的函数和基本操作 +、-、*、/。
让我们只用一个操作来构建所有功能：

a + a
a + b
a - a
a - b
a * a
a * b
a / a
a / b

我想很容易看出其中一些函数更有意义，因为其他一些函数可能是相等的，但至少，它是一个可以通过循环生成的映射。

现在在下一次迭代中，可以轻松地添加到这些功能中的每一个

• 具有所有操作的现有参数之一
• 包含所有操作的第三个参数

之后，您有一个庞大的功能列表，您可以为其重复第二步。

由于 是一个估计所有更复杂函数的函数，如 sin 和 log（泰勒级数），因此这些函数也应该包含在这个函数空间中。

这有帮助吗？随意编辑这篇文章！

只需重新阅读您的帖子。如果您想枚举所有编程函数而不仅仅是数字一次，我想它会更复杂。我想那么通过压缩函数的源并将zip文件视为一个大数字来使用映射“函数<->数字”是有意义的。反过来，您可以尝试解压缩任何数字，看看它是否会创建一个有用的功能 :-) 但我想您会有很多数字，甚至不是 zip 文件。

但这将满足您的要求，即每个函数都有一个代表它的数字:-)

Answer 5

您可以采用任何编程语言，以便您可以确定某物是否是程序，并按字典顺序列出所有程序。为了避免至少一点组合爆炸，您可以以规范化的形式分配用户定义的名称（变量、函数等）。显然，这将产生大量的功能，而且要挑选出哪些功能真正有用并不容易。任何自动修剪方法都将排除您实际需要的某些功能，或者无法将组合爆炸修剪到足够有用的程度，或者两者兼而有之。

这样做的另一个缺点是从数字到函数将非常困难：很难找到比枚举大约四百千万亿个函数更好的方法来找到函数 433,457,175,432,167,463。

另一种方法是通过将符号映射到数字并有效地将它们连接起来，将函数编码为数字。

假设符号为 +、-、:=、==、<、if、then、endif、do、end_do_condition、enddo 和语句分隔符。那里有 11 个符号，没有变量，这是一个非常小的集合，不包含函数调用之类的任何东西，并且需要你自己乘除。（如果没有一两个逻辑运算符，我实际上不确定这是否可行。）添加五个变量名，您就拥有了一种具有 4 位字符的编程语言。这意味着最多十六个字符将适合 64 位无符号整数。

一旦你掌握了这个，函数之间所有可能的关系都将可以表示为算术关系，但这是一个非常复杂的关系，在实践中很难做到正确。

简而言之，虽然这在理论上是可行的，但在实践中将过于笨拙。用您选择的非功能语言为功能语言编写解释器可能会更容易。

Answer 6

要编写这样一个函数，可以采用任何图灵完备的语言（编程语言编译器、lambda 演算、图灵机..​​....）并枚举所有程序

我不太确定这是否可以做到……感觉这与图灵-教会论点背道而驰。为了枚举所有程序，首先您需要一个算法来确定哪些程序有效，哪些程序无效，这是不可能的……除非您不关心这一点并允许您的语言使用不正确的程序。

但也许正式系统的哥德尔化可以帮助你......我会尝试使用 Lisp，将代码作为数据会有很大帮助。

Answer 7

不确定我是否理解。但有一件事 - 你不能枚举所有可能的可计算函数。简短的回答：因为否则会有一个通用的防病毒软件。长答案：因为如果存在这样的枚举，那么您将在该集合中还有计算枚举本身的函数。就像罗素悖论一样。

你的问题的一个不同的答案是——你想“列出”所有可能的可计算函数；为此，您可能希望将它们表示为素数，并将它们的组合用作乘法。这将保证唯一性。因式分解将为您提供相反的功能。