0

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

4

6 回答 6

2

你的问题措辞含糊。

您将如何指定“程序应该做什么”？
程序功能的任何精确、完整和机器可读的规范都已经是程序。

因此，您的问题的答案是，编译器。

现在，您要问的是如何根据输入和输出的样本来查找函数。
这是一个我无法回答的关于统计分析的问题。

于 2011-11-25T03:12:38.347 回答
2

有了这些沉思，一个人必须非常小心。由于没有清楚地区分命题成立的程序或x命题P(x)成立的任何程序x，造成了很多混乱P(x)。只要P(x)持有的程序集是有限的，就总有一个证明，证明它们的正确性（尽管这个证明可能不为人知）。

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

采取 10 个程序，它们不接受任何输入，可能会也可能不会终止并产生“hello World”。然后有一个程序可以准确地确定这些程序中哪些是正确的，哪些不是。让我们调用这些程序(x_1,...,x_10)。如果设置了 i 的二进制表示中的第 j 位，则取程序的(X_0,...,X_{2^10})输出X_i。这些程序中的一个必须是对所有十个正确决定的程序，可能没有任何方法可以确定这 100 个中的哪一个是正确的（此时是一个元问题）。truex_jx_iX_j

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

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

于 2011-11-25T09:35:56.187 回答
1

听起来您想生成一个状态机，该状态机通过给定输入序列进行学习，然后自我更新以产生适当的输出序列。假设您的输出序列对于相同的输入序列总是相同的，那么编写起来应该足够简单。如果您的输出不是确定性的，例如根据一天中的时间更改输出，则您无法自动生成状态机。

于 2011-11-25T03:39:16.110 回答
1

取决于您所说的“一对一映射”是什么意思。（而且，我想，“输入”和“输出”。）

我的猜测是，您要问的是，给定给定任意程序的输入和输出示例，是否可以设计一种算法来编写等效程序？如果是这样，答案是否定的。例如，您可以有一个输入/输出为 1/1、2/2、3/3、4/4 的程序，但如果下一个输入值为 5，则输出将为 3782。没有办法从一组给定的结果中知道下一个结果可能是什么。

于 2011-11-25T03:55:46.113 回答
1

由于您没有说明输入和输出的呈现方式，因此该问题未指定。对于有限列表，答案是“是”，如以下 Python 代码所示：

def f(input,output):
    print "def g():"
    print "    x = {" + ",".join(repr(x) + ":" + repr(y) for x,y in zip(input,output)) + "}"
    print "    print x[raw_input()]"


>>> f(['2','3','4'],['a','b','x'])
def g():
    x = {'2':'a','3':'b','4':'x'}
    print x[raw_input()]
>>> def g():
...     x = {'2':'a','3':'b','4':'x'}
...     print x[raw_input()]
... 
>>> g()
3
b

对于无限集，您将如何呈现它们？如果您只显示一小部分输入样本，则不会指定整个算法。猜测最合适的人是无法确定的。如果你有一个“魔法黑盒”，那么会有很多连续的映射，但只有可数的程序，所以这是不可能的。

于 2011-11-25T09:14:34.427 回答
0

我想我同意 SLaks，但是从不同的角度来看，编译器是做什么的？

（编辑：我看到 SLaks 编辑了他的原始答案，基本上是“你在描述身份函数”）。

它采用一种源语言来描述程序的预期行为，然后用表现出该行为的目标语言“编写”另一个程序。

我们也可以从流程细化等方面来考虑这一点——给定一个抽象规范，我们可以构建一个细化映射到一些“更具体的”（通常读作：更少的非确定性）实现。

但是根据您的问题，很难说出您的意思是哪一个（如果有的话）。

于 2011-11-25T03:16:16.723 回答