是否有迭代编写新程序的程序？

Question

大约一年来我一直在考虑编写一个可以编写程序的程序。这主要是一个有趣的练习，可能会教我一些新概念。我的灵感来自负熵以及从混乱中产生秩序以及从混乱中产生新的混乱的能力无限连续的顺序。

更具体地说，该程序将首先写入一个短的随机字符串。如果字符串编译，程序将记录它以供以后比较。如果字符串未编译，程序将尝试重写它，直到编译为止。随着更多字符串（迷你“无用”程序）被记录，它们可以被解析以查找相似性并用于生成语法。然后可以利用该语法来编写更多比纯随机字符串具有更高编译概率的字符串。

这显然有点愚蠢，但我认为尝试开发这样的程序会很有趣。作为副产品，我得到了一堆独特的程序，我可以将它们可视化并称之为艺术。

由于其简单的语法和动态编译，我可能会用 Ruby 编写此代码，然后我将使用 ruby​​ 处理来可视化处理过程。

我想知道的是：

• 这种类型的编程有名称吗？
• 目前该领域存在什么？
• 主要贡献者是谁？
• 奖金！ - 除了编译之外，我可以通过哪些方式在程序上为输出程序赋值（y/n）？
  我可能想扩展该程序的功能以生成基于参数的程序，但我希望该程序通过运行编译的程序并为程序输出分配含义来定义这些参数。这个问题可能比奖金的合理性更复杂，但如果您能想出一种简单的方法来在不到 23 行或一个超链接的时间内完成类似的事情，请把它扔到您的回复中。

我知道这不完全是元编程，根据我对人工智能和生成算法的了解，它们通常比我想象的更以目标为导向。最好的是一个能够不断重写和改进自身的程序，这样我就不必^_^

Answer 1

查找“基因编程”。

编辑以回复评论：

@chris，@Kasturi：正确。 OP中描述的是一个通过暴力尝试编译某些具体语法来推断语法的系统，然后从该语法中反向生成新的具体语法。如果您一定有一些与该描述非常匹配的东西......我最好的建议是考虑使用某种语言的具体语法以非常少的语法构建隐藏的马尔可夫模型。我会考虑使用最小的组合逻辑（本质上类似于 Unlambda 语言）。

另一方面，遗传编程是一种具有一定成熟实践和文献的技术，并且不是“确定性”的，而是一个随机过程。这也是一个相当广泛的术语——可以说 OP 系统是 GP 的一个极限情况，具有 0% 交叉和 100% 突变。

Answer 2

您听说过nanopond吗？这个概念和你的类似。每个像素都有一个随机生成的字符串，该字符串通过编译器运行。通常，这不会产生任何有效的程序。然而，每隔一段时间，随机生成的字符串就会以某种方式完美地格式化，以便能够将其自身复制到相邻像素中。很快，这就变成了一场争夺哪个程序能够比另一个程序更好地重现的战斗。

是的，你所说的是遗传算法，但最大化一件事，而且只有一件事：繁殖能力。

这是所有自然发生的负熵现象的基本起源：随机形成的复杂实体具有繁殖能力。

经典遗传算法强加了人工繁殖标准——人工选择表现最好的程序来进行繁殖。

你所暗示的是一种计算自然选择。也就是说，程序将根据其自我复制的能力来进化，仅此而已。

这会创造出有用的东西吗？也许不是。除非您允许您的程序访问互联网或其他一些它们可以随机访问的外部 API，并且可能通过互联网传播。

不幸的是，您所描述的系统仍然有一些人为的复制标准：编译的能力。

因为编译能力=重现能力，所以你人为地将你的程序设置为朝着编译的方向发展。

编译什么？这并不重要，因为任何编译后的程序都可能像上一个程序一样重现。假设您以某种方式生成了一个可以输出斐波那契数列的程序。或者一个可以击败国际象棋大师的程序。凉爽的！不幸的是，它会被复制吗？会不会很特别？

一点也不;它会被视为“适合”复制，因为程序 print('k')

我建议也许操作一个随机运行的程序字符串框架，这些程序可以访问 API，这些 API 可以：

• 读取/写入硬盘驱动器，突然之间，您就有了可以将随机字符串写入程序本身的程序。
• 删除/修改硬盘上的其他文件；这使得程序可以相互竞争。您的 API 可以设计为仅当程序的“强度”（任意值……可能是字符长度）强于文件时才能删除该文件。
• 在硬盘驱动器上运行其他脚本...甚至可能是他们自己编写的脚本
• 访问互联网；到网络服务器？能够编写/附加/发送/阅读电子邮件吗？

我认为编写可以自我复制的程序的程序比编写可以编译的程序可以产生更好的结果。

除非你只想要后者；那么也许你可以最大化程序长度。但有可能发生一些有趣的事情吗？没那么多；任何“编译”具有一定长度的程序都与“复制”一样可能。

Answer 3

您可以做的另一个项目是处理从未通过某个单元测试到通过单元测试的转变。

例如，给定一个实现，

def add(a,b)
  a
end

您可以添加一个测试

assert_equal 3, Foo.new.add(1,2)

，并要求您的程序尝试 add 中的 a 上的方法的任意组合（例如，a.-( b)、a.to_s、a.+(b))，直到其中一个突变体通过该测试和现有测试。

您可能想查看 heckle （或 Zentest？）以获取更改正在测试的代码的示例。

Answer 4

查找语法演变。

Answer 5

最好的是一个程序
不断重写和改进
本身，所以我不必

执行这些步骤：

1. 在汇编中编写伪随机数生成器。 （实模式）
2. 修改程序，使其写出（例如）64k 随机数并对第一个字节执行 FAR JMP。
3. （可选）为看门狗定时器创建驱动程序以防止无限循环
4. 加载到某些设备的引导扇区。
5. 获取多台计算机。配置以便如果它们发生三次故障，它们将重新启动并从设备的引导扇区启动
6. 启动计算机并等待几十年（或几个世纪，无论什么）它会产生有用的东西
7. 利润！

Answer 6

早期但非常有趣的作品是 Doug Lenat 的“AM”（数学家）和 Eurisko （AM 的概括）。

Eurisko 通过研究边界条件如何影响问题的解决，发展了一套色调学。它不会产生垃圾，而是尝试一下，相反，它采用了一种较弱的问题解决方法，发现了可以做得更好的情况，并生成了问题解决程序的修补版本。