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

Question

动机:我希望能够在没有一阶函数的语言中使用玩具函数式编程,使用自然数而不是函数.

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

要编写这样的函数,可以使用任何图灵完备语言(编程语言编译器,lambda演算,图灵机......)并枚举所有程序.我不仅要考虑评估,还要考虑添加,构图,曲线等功能.例如,给定两个函数f的指数,g我想知道函数f + g的索引是什么,或者f由g组成.这将允许"玩具功能编程".

编写这样的代码库有什么好方法？我不是在寻找一个极简主义的Turing tarpit,它很难计算10的阶乘,也不想编写高级编译器.它应该有一些基本功能,如添加和写循环的可能性,但不多.

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

澄清:枚举函数将包含所有部分递归(可计算)函数 - 这包括不停止某些输入的函数.在这种情况下,通用功能将悬而未决; 当然这是不可避免的.另请参见:m-recursive函数 - http://en.wikipedia.org/wiki/Μ-recursive_function.

Answer 1

你想要的是一个翻译.

首先,任何具有所需属性的枚举都不适合您想要在前2 ^ 32甚至前2 ^ 64整数中操作的有趣函数.所以你需要更大的整数,在内存中分配并通过指针引用.

为什么不在任何现有语法中使用表示程序的字符数组(字符串)呢？将这样的字符串视为整数,如果这让你开心.要计算的函数的数量f1()+f2()是由(f1的表示),"+"和(f2的表示)构成的字符串.你明白了......

这种方法没有的是函数表示的唯一性,这可能隐含在你的问题中(我不确定).我确信,表示的单一性与在函数表示上进行简单甚至可计算的合成操作是不相容的 - 例如,如果不是这种情况,就会有一个简单的解决Halting问题的方法.

Answer 2

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

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

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

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

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

现在，在下一次迭代中，人们可以轻松添加到这些函数中的每一个

之后，您将获得一个巨大的函数列表，您可以重复第二步。

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

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

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

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