Writing a program that writes a program

Question

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.

Answer 1

Your question is ambiguously phrased.

How would you specify "what a program should do"?
Any precise, complete, and machine-readable specification of a program's functionality is already a program.

Thus, the answer to your question is, a compiler.

---

---

Now, you're asking how to find a function based on a sample of its input and output.
That is a question about statistical analysis that I cannot answer.

Answer 2

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).

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:

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).

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.

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.

Answer 3

Sounds like you want to generate a state machine that learns by being given an input sequence and then updates itself to produce the appropriate output sequence. Assuming your output sequences are always the same for the same input sequence it should be simple enough to write. If your output is not deterministic, such as changing the output depending on the time of day, then you cannot automatically generate a state machine.

Answer 4

Depends on what you mean by "one to one mapping". (And also, I suppose, "input" and "output".)

My guess is that you're asking whether, given an example of inputs and outputs for a given arbitrary program, can one devise an algorithm to write an equivalent program? If so, the answer is no. Eg, you could have a program with the inputs/outputs of 1/1, 2/2, 3/3, 4/4, and yet, if the next input value was 5, the output would be 3782. There's no way to know, from a given set of results, what the next result might be.

Answer 5

The question is underspecified since you did not say how the input and output are presented. For finite lists, the answer is "yes", as in this Python code:

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

for infinite sets how are you going to present them? If you show only a small sample of input this does not specify the whole algorithm. Guessing the best fit is undecidable. If you have a "magic blackbox" then there are continuum many mappings but only a countable number of programs, so it's impossible.

Answer 6

I think I agree with SLaks, but taking things from a different angle, what does a compiler do?

(EDIT: I see SLaks edited his original answer, which was essentially 'you're describing the identity function').

It takes a program in one source language that describes the intended behaviour of a program, and "writes" another program in a target language that exhibits that behaviour.

We could also think of this in terms of things like process refinement --- given an abstract specification, we can construct a refinement mapping to some "more concrete" (read: less non-deterministic, usually) implementation.

But based on your question, it's really very difficult to tell which of these you meant, if any.