编写一个程序，写一个程序 [英] Writing a program that writes a program

问题描述

其理论计算机科学的世界，你好测试仪计划是一个不可判定的问题是众所周知的。（这是的的Hello World测试仪
我的问题是，因为给出一个程序作为输入，我们不能说什么程序会做什么，我们就可以解决了相反的问题：
的鉴于集的输入和输出的，是有一种算法将程序写入写入的程序来实现给定的输入和输出之间的一对一的映射。
我知道元编程但我的问题是更多的理论兴趣。一些东西，可以申请一个通用的案例。

Its well known in theoretical computer science that the "Hello world tester" program is an undecidable problem.(Here is a link what i mean by hello world tester
My question is since given a program as input we can't say what the program will do,can we solve the reverse problem:
Given set of input and output,is there an algorithm for writing a program that writes a program to achieve a one to one mapping between the given input and output.
I know about metaprogramming but my question is more of theoretical interest. Something which can apply for a generic case.

推荐答案

使用这类沉思中的一个必须非常小心。很多困惑源于没有明确区分有关 节目 X 为其命题 P（x）持有或任何节目 X 为其命题 P（x）持有。只要一套方案，其中 P（x）认为是有限的存在始终是他们的正确性的证明，（尽管这证明可能不知道）。

With these kind of musings one has to be very careful. A lot of confusion arises from not clearly distinguishing about a program x for which proposition P(x) holds or any program x for which proposition P(x) hold. As long as the set of programs for which P(x) holds is finite there always is a proof, of their correctness (although this proof may not be known).

在这一点上你也有计划，这是和可以知道和方案只能显示所有posibilities完全枚举存在区别开来。让我们一个例子：

At this point you also have to distinguish between programs, which are and can be known and programs which can only be shown to exist by full enumeration of all posibilities. Let's make an example:

取10程序，它拿不出输入和可能会或可能不会终止而产生的Hello World。再有就是一个程序，决定到底是哪这些方案是正确的，哪些不是。让我们把这些程序（X_1，...，x_10）。将做好的节目（X_0，...，X_ {2 ^ 10}），其中 X_i 输出真的节目 x_j ，如果在我的二进制重新presentation的第j个位。其中一项方案必须是其中一个决定正确的所有十个 x_i ，也只是可能没有任何办法来不断找出这100 <$ C $的哪一个C> X_j s是正确的（在这一点上的元问题）。

Take 10 Programs, which take no input and may or may not terminate and produce "hello World". Then there is a program which decides exactly which of these programs are correct, and which aren't. Lets call these programs (x_1,...,x_10). Then take the programs (X_0,...,X_{2^10}) where X_i output true for program x_j if the j-th bit in the binary representation of i is set. One of these programs has to be the one which decides correctly for all ten x_i, there just might not be any way to ever figure out which one of these 100 X_js is the correct one (a meta-problem at this point).

这正好说明，考虑到有限的套节目和输入/输出对人们总是可以解决充分枚举和paradoxies全部停机，问题类型瞬间消失。你的情况设定为每个输入产生程序的大小为1和组输入/输出对有限大小的（因为你必须把它提供给元程序）的。因此，全枚举解决您的问题很简单，你也可以修正程序很容易证明两者的正确性，以及元程序的正确性。

This goes to show that considering finite sets of programs and input/output pairs one can always resolve to full enumeration and all halting-problem type of paradoxies instantly disappear. In your case the set of generated programs for each input is of size one and the set of input/output pairs is of finite size (because you have to supply it to the meta-program). Hence full enumeration solves your problem very simple and you can also easily proof both the correctness of the corrected program as well as the correctness of the meta-program.

注：由于该组生成的程序是无限的，这是为数不多的案例之一，你可以证明 P（x）一组无限的程序（实际上你能证明 P（X，输入，输出）此设置）。这表明，该组是无限是只有一个必要的，而不是充分条件这一类型悖论出现。

Note: Since the set of generated programs is infinite, this is one of the few cases where you can proof P(x) for a infinite set of programs (actually you can proof P(x,input,output) for this set). This shows that the set being infinite is only a necessary, not a sufficient condition for this type of paradoxes to appear.

这篇关于编写一个程序，写一个程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！