计算机自动编程--路在何方?
脱离解决问题的具体过程,仅通过向计算机描述所需程序需满足的功能,从而让计算机自己生成解决问题的方法,这无疑是计算机编程方式的必然方向。我在下文里将会称其为计算机自动编程。
曾经在csdn等处看到几篇关于计算机自动编程的文章,提出了一些设想,但它们总离不开一点,那就是计算机自动编程是要建立在未来计算机强大的计算能力之上的,因为它或多或少要和人工智能扯上联系。这样的未来真让人沮丧,因为知道现在计算机似乎还没有一点“智能”的影子,即使有了又会怎样呢?它的效率如何?它会不会继承人类智慧的缺陷呢?比如,它编出来的程序会不会也出现bug?
但仔细分析这个问题,前景或许没那么黯淡。
让我们回到第一段:
通过向计算机描述所需程序需满足的功能,从而让计算机自己生成解决问题的方法。
看来,计算机自动编程需要解决两个重大问题:
一是如何建立一种语言,用它来描述程序的功能。这种语言最好是高于现在的编程语言的,因为它不对解决问题的具体过程作出描述,我们不妨称之为“面向功能”的语言。
二是如何让计算机自己找到解决问题的办法。这无疑才是最重要的问题,我们要往下探索的也正是这个。
第一个问题中的语言是完全可以让现有语言代替的--几乎所有问题都可以用一种程序化的办法获得其解决算法,那自然就是穷举(当然也有例外,比如输出只有一个bit的算法就不行)。我们可以毫不费力的用穷举法写出某个问题的解决算法,这个算法就已经包含了要实现功能的全部描述。
下一步要做的,就是如何把这个笨的恐怖的算法转化为一个低时间复杂度的算法。到此,第二个问题就转化为:
如何进行算法化简?
或许可以说,解决了这个问题就解决了计算机自动编程的问题。
每个算法都可以实现一个函数,尽管它或许是处理字符串之类数据类型的函数,我们是可以用编码将其定义域/值域映射到自然数集N上的。换句话说,每个算法所实现的功能,都可以用数论函数来表示。
这样,算法的化简,其实也就是其对应函数的化简。
要实现算法化简,必然要求找到一系列算法之间变换的规则(这里的算法必须是计算相同的函数的,我们将称之为等效算法),这类似于数学上的运算律,而事实上,数学中的运算律也正是来自于这组规则的。
那我们可以问很多问题,比如,这会是一组很简单的规则吗?使任一个算法都可以变换到它的任意等效算法的规则存在吗?是不是所有的算法都可以化简?
我们先来看第二个问题:使任一个算法都可以变换到它的任意等