列举计算机程序是可能的吗?

function find_truth(){
    for(n=0;;++n){
        try {
            var fn = Function(string(n));
            if (fn() == 42)
                return fn;
        } catch() {
            continue;
        }
    }
}

是的，这是有可能的。几个月前，我做了一个类似的小实验项目，考虑到它的作用，它的效果相当不错。你给它一个类型和一些要通过的测试，它会搜索一个通过测试的合适函数。我从来没有做过使它成熟的工作，但是您可以看到，它实际上最终生成了通过示例测试的函数。要求这种类型是这种搜索的实用性的一个重要组成部分——它大大减少了需要尝试的程序的数量。

在断言什么是可能的，什么是不可能的之前，对理论有一个牢固的掌握是很重要的——有很多人会跳到令人犹豫的问题上，告诉你这是不可能的，而事实远比这微妙得多。

• 您可以轻松地用给定语言生成所有语法上有效的程序。简单地说，你可以生成所有字符串并过滤掉那些需要解析/类型检查的字符串;但是有更好的方法。
• 如果语言不完整——例如简单类型的lambda演算，或者甚至像Agda这样非常强大的东西，你可以列举所有生成42的程序，并且给定任何程序，你可以决定"这生成42";或者"这不会产生42"。(我在实验项目中使用的语言就是这门课)。这里的紧张之处在于，在任何这样的语言中，都会有一些你无法编写的可计算函数。
• 即使语言即将完成，你仍然可以枚举所有最终生成42的程序(通过并行运行它们，并在它们完成时报告成功)。

对于一个图灵完备的语言，你不能做的是决定一个程序绝对不会生成42——它可以永远运行下去，直到它成功，你才知道它最终是否会成功。有一些程序可以判断为无限循环，但不是全部。因此，如果您有一个程序表，您可能期望您的枚举器程序在非图灵完备语言的情况下是这样的:

Program |  P1  |  P2  |  P3  |  P4  |  P5  |  P6  |  P7  | ...
42?     | No   | No   | No   | Yes  | No   | No   | No   | ...

而在图灵完备语言中，您的输出(在给定时间)将是这样的:

Program |  P1  |  P2  |  P3  |  P4  |  P5  |  P6    |  P7  | ...
42?     | No   | No   | Loop | Yes  | No   | Dunno  | No   | ...

然后这个"不知道"可能会变成"是"或"否"，或者永远都是"不知道"——你就是不知道。

这些都是理论性的，实际上用图灵完备的语言生成程序来搜索做某件事的程序是相当困难的，需要很长时间。当然你不想一个一个地做，因为空间太大了;你可能想使用遗传搜索算法或其他东西。

理论中的另一个微妙之处是:谈论那些"生成42"的程序。漏掉了一些重要的细节。通常当我们讨论生成程序时，我们希望它生成一个特定的函数，而不仅仅是输出特定的东西。这就是你想做的事情变得越来越不可能的时候。如果你有一个无限的可能输入空间——比如说，输入一个数字，那么

• 一般来说，你不能告诉程序是否计算给定的函数。你不能手动检查每一个输入，因为无穷大太多了。你不能寻找证明你的函数做正确的事情，因为对于任何可计算函数f，对于任何公理系统A，有计算f的程序，使得A没有证明它们计算f。
• 你无法判断一个程序是否会对每一个可能的输入给出任何类型的答案。它可能对其中的前400,000,000起作用，但对第400,000,001起无限循环。
• 同样，你无法判断两个程序是否计算相同的函数(即相同的输入->输出相同)。

这就是可决定理论现象学的每日剂量。

如果您对真正的操作感兴趣，请查看遗传算法，并在您尝试的函数上设置超时和/或使用可确定的(非图灵完备的)语言。

当然可以枚举给定语言中语法有效的所有程序(在静态类型语言中甚至只有那些进行类型检查的程序):您可以简单地枚举所建议的所有字符串，尝试将每个字符串提供给该语言的解析器，然后拒绝那些无法解析的字符串。因此，如果这是你对有效程序的定义，那么是的，这是可能的。

然而，你的程序最终不一定会输出一个返回42的函数——即使你用一个只返回语法上有效的程序的函数来替换string。如果返回的函数包含无限循环，则它将永远运行，因此您的程序将永远无法尝试另一个函数。因此，您可能永远无法得到返回42的函数。

为了避免这个问题，你可能会说string(n)函数应该只产生语法上有效的代码和不包含无限循环(同时仍然能够返回所有这样的函数)。然而，这是不可能的，因为这需要解决停止问题(当然，这是无法确定的)。

如所述，通过插入X语言的解析器/编译器，您可以轻松地将"生成所有字符串"程序转换为"以X语言生成所有有效程序"。通常，如果您可以编写一个以文本作为输入并返回true/false指示文本是否代表有效程序的程序，那么您可以将其用作"生成所有字符串"程序的过滤器。

您也可以设计一种编程语言，其中每个字符串都是一个有效的程序(想到perl)。

可能更有趣的是，给定一种语言的形式语法，您可以使用该语法在该语言中生成程序，而不是解析它们。您只需要对语法进行宽度优先遍历，以确保在有限的时间内到达每个有限长度的程序(如果您进行深度优先遍历，您将在探索仅由变量组成的所有程序时遇到困难，该变量的名称是一个越来越长的"a"序列或其他东西)。

实际上在解析编程语言中使用的大多数语法都不能直接用于此;他们通常有点过于宽容。例如，语法可以将标识符定义为匹配regex [_A-Za-z][0-9_A-Za-z]*的任何内容，它允许无限长度的变量名，但是许多语言实现实际上会对具有千兆字节长度的变量名的程序造成阻塞。但原则上，您可以找出所有这些陷阱，并编写一个可枚举的语法，该语法准确地涵盖了某种感兴趣的语言中的所有有效程序。

---

这样就可以枚举所有的程序。这实际上不足以让你运行find_truth程序并找到一个返回42的程序，因为它会无限地计算碰巧包含无限循环的第一个程序。

但是仍然实际上可以这样做!你只需要选择一个顺序来检查所有的可能性，这样所有的事情最终都会在有限的时间内完成。你有两个无限的"维度"去搜索;枚举所有程序，并对每个程序进行深度评价。您可以通过以下策略来确保您涵盖了所有基础:

1. 运行长度为1的所有程序，最多1步
2. 运行长度不超过2的所有程序，最多2步
3. 运行长度不超过3的所有程序，最多3步
4. …

以此类推。这保证了无论程序的长度和所需的"步骤"的数量如何，您最终都将实现它们，而无需"首先"完成无限的工作(只要具有所需结果的程序确实存在)。

如果你有无限的可用存储空间，你可以避免在这些阶段之间重复工作(你存储所有长度为N的程序，在N步内没有完成，以及它们的状态，然后在下一轮运行新程序，最多N+1步，并运行所有"挂起"的程序，每一步多走一步)。"步"的定义并不重要，只要它不允许无限循环。一些有限数量的字节码，或者CPU指令，甚至是秒;当然，您需要该语言的可暂停实现。

假设我正确地理解了您的短语"枚举程序本身是可能的吗?"然后是您可以枚举程序。这本质上是一个遗传规划问题。参见:

http://en.wikipedia.org/wiki/Genetic_programming

这里程序本身被创建、运行和评估(使用结果适应度值，其中最优值= 42)，就像使用遗传算法一样，所以这将提供您的枚举。此外，经过几代，你可以让它进化你的程序产生42 .

这是不可能的。问题是，一些程序可能需要很长时间才能完成计算。有些程序可能会陷入无限循环。理想情况下，您希望中止运行那些陷入无限循环的程序，只保留长时间运行的程序。您可以实现一个计时器，但是如果您的程序运行时间比计时器长，但仍然会返回正确的答案呢?

一般来说，判断一个计算机程序是否会终止的唯一方法是冒着进入无限循环的风险运行它并观察。当然，您可以实现一些启发式方法来识别常见的无限循环形式，但通常这是不可能的。这就是所谓的停机问题。

编辑:

我意识到我只是部分地回答了你的问题。你问是否有可能枚举程序本身。这当然是可能的。您已经有了一种按顺序生成所有可能字符串的方法。然后你就可以看到哪些字符串可以作为javascript程序正确解析，并保留它们。

我建议从javascript的语法开始，例如ANTLR。

https://github.com/antlr/grammars-v4/blob/master/javascript/javascript/JavaScriptParser.g4

语法定义了一个类似于下面的有向图:

grammar Exp;
/* This is the entry point of our parser. */
eval
    :    additionExp
    ;
/* Addition and subtraction have the lowest precedence. */
additionExp
    :    multiplyExp 
         ( '+' multiplyExp 
         | '-' multiplyExp
         )* 
    ;
/* Multiplication and division have a higher precedence. */
multiplyExp
    :    atomExp
         ( '*' atomExp 
         | '/' atomExp
         )* 
    ;

使用这个结构，你可以创建一个程序，创建所有语法上有效的程序不同深度1,2,3,4，…并在模拟器中运行。这些都是语法上有效的程序，尽管许多程序会返回错误(例如除零或访问未定义的变量)。还有一些你无法证明他们是否完成了。但是，使用像ANTLR提供的那样正确定义的语法，生成尽可能多的语法正确的程序是可能的。