11

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

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

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

由于其简单的语法和动态编译，我可能会用 Ruby 编写它，然后我将使用 ruby​​-processing 在处理中进行可视化。

我想知道的是：

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

我知道这不是元编程，而且根据我对人工智能和生成算法的了解，它们通常比我想象的更面向目标。最佳方案是不断重写和自我改进的程序，所以我不必^_^

4

6 回答 6

6

查找“基因编程”。

编辑以回应评论：

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

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

于 2010-06-15T18:16:00.373 回答
5

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

你说的是遗传算法，是的，但是最大化一件事和一件事：繁殖能力。

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

经典的遗传算法强加了人为的繁殖标准——人为地选择最能完成工作的程序进行繁殖。

您的意思是一种计算自然选择。也就是说，程序将根据它们自我复制的能力而发展，仅此而已。

这会创造一些有用的东西吗？也许不是。除非你，也许，让你的程序访问互联网或其他一些他们可以随机访问的外部 API，并可能在互联网上传播。

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

因为编译能力=复制能力，你已经人为地设置你的程序向编译方向发展。

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

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

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

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

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

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

于 2010-06-16T01:38:14.030 回答
1

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

例如，给定一个实现

def add(a,b)
  a
end

你可以添加一个测试

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

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

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

于 2010-06-16T01:01:27.050 回答
1

寻找语法进化。

于 2010-06-16T01:54:36.033 回答
0

最佳方案是不断重写和自我改进的程序，因此我不必

执行以下步骤：

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

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

Eurisko 通过检查边界条件如何影响解决问题，发展了一套启发式方法。它没有产生垃圾而不是尝试，相反，它采用了一种弱问题解决方法，并找到了可以做得更好的案例，并产生了问题解决程序的补丁版本。

于 2010-06-19T16:58:25.290 回答