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

Question

大约一年来,我一直在考虑编写一个编写程序的程序.这主要是一个有趣的练习,可能会教我一些新的概念.我的灵感来自于negentropy和秩序从混乱和新的混乱中出现的能力,无序地连续出现.

更具体地说,程序将从编写一个短随机字符串开始.如果字符串编译程序将记录它以供以后比较.如果字符串没有编译,程序将尝试重写它,直到它编译.随着更多字符串(迷你'无用'程序)被记录,可以解析它们的相似性并用于生成语法.然后可以使用该语法编写更多的字符串,这些字符串具有比纯随机字符串更高的编译概率.

这显然不仅仅是一点点愚蠢,但我认为尝试发展这样的程序会很有趣.作为副产品,我得到了许多独特的程序,我可以想象并称之为艺术.

由于其简单的语法和动态编译,我可能会在Ruby中编写这个,然后我将在使用ruby处理的处理中进行可视化.

我想知道的是:

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

我知道这不是元编程,从我对AI和生成算法的了解很少,他们通常比我想的更注重目标.什么是最优的是一个不断重写和改进自己的程序,所以我没有必要^ _ ^

Answer 1

查找"遗传编程".

编辑以回复评论:

@chris,@ Kasturi:是的.OP中描述的是一个用于通过暴力尝试来推断语法的系统,以使得一些具体的语法编译,然后从语法中反向生成新的具体语法.如果你必然会有一些与这个描述非常接近的东西...我最好的建议就是用一些语言用非常小的语法从具体语法中构建一个隐藏的Markov模型.我考虑使用最小的组合逻辑(类似于Unlambda语言的精神).

另一方面,遗传编程是一种具有一些发达的实践和文献的技术,并不是"确定性的",而是一个随机过程.这也是一个相当广泛的术语---可以说OP的系统是GP的限制性案例,具有0%交叉和100%突变.

Answer 2

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

你所谈论的是遗传算法,是的,但最大化一件事和一件事:重现的能力.

这是所有自然发生的negentropic现象的重要起源:随机形成的复杂实体具有繁殖能力.

经典的遗传算法强加了人工繁殖标准 - 人工选择繁殖的程序是最重要的.

你所暗示的是一种计算自然选择.也就是说,程序将根据其自我复制的能力而发展,仅此而已.

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

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

因为编译能力=复制能力,所以人为地将程序设置为向编译方向发展.

编译什么？这没关系,因为任何编译的程序都可能像最后一个一样重现.假设你以某种方式生成了一个输出Fibonacci序列的程序.或者一个可以击败国际象棋大师的程序.凉!不幸的是,它会被复制吗？它会特别吗？

一点也不; 对于作为节目的复制,它被视为"适合"print('k')

我建议可能运行一个随机运行的程序字符串框架,这些程序可以访问API,可以:

• 读/写硬盘驱动器,突然之间,你有程序可以自己编写随机字符串作为程序.
• 删除/修改硬盘上的其他文件; 这允许程序可能相互竞争.您的API可以设计为只有在程序的"强度"(任意值...可能是字符长度)强于文件时才能删除文件.
• 在硬盘上运行其他脚本......甚至可能是他们自己编写的脚本
• 访问互联网; 到网络服务器？能够编写/附加/发送/阅读电子邮件吗？

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

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