algorithm - 写一个写程序的程序

Question

在理论计算机科学中众所周知，“Hello world tester”程序是一个无法判定的问题。(这是我所说的链接 hello world tester
我的问题是既然给了一个程序作为输入我们不能说程序会做什么，我们可以解决相反的问题吗:
给定一组输入和输出，是否有一种算法可以编写一个程序来实现给定输入和输出之间的一对一映射。
我知道 metaprogramming但我的问题更多的是理论上的兴趣。可以申请通用案例的东西。

Answer 1

对于这些想法，必须非常小心。很多混淆是由于没有明确区分a程序而产生的x对于哪个命题P(x)持有或任何程序x对于哪个命题P(x)捕获。只要为这一套方案P(x) holds is finite there is always an proof of them correctness(尽管这个证明可能不为人所知)。

在这一点上，您还必须区分已知和可能已知的程序，以及只能通过完整列举所有可能性来证明存在的程序。让我们举个例子:

以 10 个程序为例，它们不接受任何输入，可能会或可能不会终止并生成“hello World”。然后有一个程序可以准确地决定这些程序中哪些是正确的，哪些不是。让我们调用这些程序 (x_1,...,x_10) .然后拿节目(X_0,...,X_{2^10})其中 X_i输出 true对于程序 x_j如果设置了 i 的二进制表示中的第 j 位。这些程序之一必须是为所有十个程序做出正确决定的程序 x_i ，可能没有任何方法可以找出这 100 个中的哪一个 X_j s 是正确的(此时是元问题)。

这表明，考虑到有限的程序集和输入/输出对，总是可以解决完全枚举，并且所有暂停问题类型的悖论都会立即消失。在您的情况下，为每个输入生成的程序集大小为 1，输入/输出对集大小有限(因为您必须将其提供给元程序)。因此，完整枚举非常简单地解决了您的问题，您还可以轻松地证明更正程序的正确性以及元程序的正确性。

注意:由于生成的程序集是无限的，这是您可以证明的少数情况之一 P(x)对于一组无限的程序(实际上你可以证明 P(x,input,output) 这组)。这说明集合无限只是出现此类悖论的必要条件，而不是充分条件。