17

假设您必须编写一个程序来测试所有程序以寻找完成特定任务的程序。例如，考虑这个 JavaScript 函数：

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

只要 string(n) 返回第 n 个可能的字符串（“a”、“b”、“c”、...“aa”、“ab”...），该程序最终将输出一个函数，该函数的计算结果为42. 这种方法的问题在于它枚举了可能是或不可能是有效程序的字符串。我的问题是：是否可以自己枚举程序？如何？

4

6 回答 6

30

是的，有一些方法可以做到这一点。几个月前，我做了一个小实验项目来做类似的事情，考虑到它在做什么，它的效果相当好。你给它一个类型和一些要通过的测试，它会搜索一个合适的函数来通过测试。我从来没有投入让它成熟的工作，但你可以看到它确实最终生成了在示例的情况下通过测试的函数。要求类型是该搜索实用性的重要组成部分——它大大减少了需要尝试的程序数量。

在断言什么是可能的和不可能的之前，牢牢掌握这里的理论是很重要的——有很多人会跳到停顿的问题上，告诉你这是不可能的，而事实却更加微妙比起那个来说。

  • 您可以轻松地以给定语言生成所有语法有效的程序。天真地，您可以生成所有字符串并过滤掉解析/类型检查的字符串；但有更好的方法。
  • 如果语言不完整——例如简单类型的 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 个无限循环。
  • 同样，您无法判断两个程序是否计算相同的函数（即相同的输入-> 相同的输出）。

你有它，每日剂量的可判定性理论现象学。

如果您有兴趣真正做到这一点，请研究遗传算法，并在您尝试的功能上设置超时和/或使用可判定（非图灵完备）语言。

于 2013-05-22T23:42:02.750 回答
4

当然可以枚举给定语言中语法上有效的所有程序（并且在静态类型语言中，即使只有那些类型检查的程序）：您可以像您建议的那样简单地枚举所有字符串，尝试将每个字符串输入解析器然后拒绝那些无法解析的语言。因此，如果这是您对有效程序的定义，那么是的，这是可能的。

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

为避免此问题，您可能会说该string(n)函数只应生成语法有效且不包含无限循环的代码（同时仍能够返回所有此类函数）。然而，这是不可能的，因为这将需要决定停机问题（当然，这是无法确定的）。

于 2013-05-22T22:53:50.677 回答
4

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

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

可能更有趣的是，给定一种语言的正式语法，您可以使用它来生成该语言的程序，而不是解析它们。您只需要对语法进行广度优先遍历，以确保每个有限长度的程序都将在某个有限的时间内到达（如果您进行深度优先遍历，您会在探索所有仅由变量，其名称是一个越来越长的 'A' 序列或其他东西）。

大多数实际用于解析编程语言的语法都不能直接用于此；他们通常稍微过于宽容。例如，语法可以将标识符定义为与正则表达式匹配的任何内容[_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 指令，甚至秒；当然，您需要该语言的可暂停实现。

于 2013-05-22T23:40:41.790 回答
2

假设我正确解释了您的短语“是否可以枚举程序本身？” 然后是的，您可以枚举程序。这本质上是一个遗传编程问题。看 ：

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

在这里，程序本身被创建、运行和评估（具有生成的适应度值，其中最佳值 = 42），就像遗传算法一样，所以是的，这将提供您的枚举。此外，经过几代人，您可以让它发展您的程序以生成42.

于 2013-05-23T07:24:17.227 回答
0

It is impossible. The problem is that some programs may take a long time to finish computing. And some programs may be stuck in an infinite loop. Ideally you would like to abort running those programs that are stuck in infinite loops, and keep only the long running programs. You could implement a timer, but what if you had a program that ran longer than the timer, but still would return the correct answer?

In general, the only way to see if a computer program will terminate is to run it and see, with the risk of entering an infinite loop. Of course, you could implement some heuristics to recognize common forms of infinite loops, but in general it is impossible. This is known as the halting problem.

EDIT:

I realize that I only partially answer your question. You ask if it is possible to enumerate programs themselves. This is certainly possible. You already have a way of generating all possible strings in order. Then you could just see which strings parse correctly as a javascript program, and just keep those.

于 2013-05-22T22:59:45.563 回答
0

我建议从 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 提供的语法）可以生成尽可能多的语法正确的程序。

于 2021-09-07T13:31:05.797 回答