views:

160

answers:

3

is it possible to write a program which prints its own source code utilizing a "sequence-generating-function"?

what i call a sequence-generating-function is simply a function which returns a value out of a specific interval (i.e. printable ascii-charecters (32-126)). the point now is, that this generated sequence should be the programs own source-code. as you see, implementing a function which returns an arbitrary sequence is really trivial, but since the returned sequence must contain the implementation of the function itself it is a highly non-trivial task.

this is how such a program (and its corresponding output) could look like

#include <stdio.h>

int fun(int x) {
    ins1;
    ins2;
    ins3;
    .
    .
    .
    return y;
}

int main(void) {
    int i;
    for ( i=0; i<size of the program; i++ ) {
        printf("%c", fun(i));
    }
    return 0;
}

i personally think it is not possible, but since i don't know very much about the underlying matter i posted my thoughts here. i'm really looking forward to hear some opinions!

+1  A: 

What you're referring to is a QUINE. Wiki's article on it is pretty good, with some helpful links. http://en.wikipedia.org/wiki/Quine_%28computing%29

glowcoder
i already tagged my question with 'quine', you see :P. i think a "common" quine works totaly different. if i'm wrong, then please show me one which works exactly the way i described. i, for myself, wasn't lucky to find one yet..
guest
I don't see why couldn't. If your function stored a character array with the source of the program in it, it would work just fine. It would, in fact, be very similar to the first C example in the wiki page.
glowcoder
the point is, that the function produces the output "mathematically", without storing anything! so when i call the function with ascending values: fun(0)=35='#', fun(1)=105='i', fun(2)=110='n', and so forth..
guest
No, you cannot access something that's never stored. I guess you could read the file directly? It's incredibly unlikely to have a mathematical function that fits your curve. You'd have to make a N order equation, where N is the number of characters in your program, feed the values into a program that solves for curves (note, this will be on the order of thousands!) and put that as your function. The problem is, doing this will change the source code, which will then change the function required. You'd have to repeat the process until it "converged" on a solution, which may never happen.
glowcoder
exactly what i was trying to say!. alltough i'm sure there could be a certain programming language, which could solve this problem (because it is in the end a matter of syntax!). even if it could only do that then..
guest
@glowcoder You are incorrect. Your faulty argument could be used to show there are no quines, but quines exist. Any Turing complete language can do what is asked.
@guest It makes no difference whether you use an array or a function. Writing a function like: `if (x==0) { return a;} else if (x==1) { return b;} else ...` is just a different notation for writing an array. If you can do it with an array, you can do it with a function.
@user207442 he is trying to do it without an array. What he means is where you could use a mathematical function like f(x)=x^3+2x^2-3x+7 and get the correct character from it. My argument could not be used to show there are no quines: merely that the process to create a quine using `that method` is unreliable and may not produce a result.
glowcoder
@flowcoder Any array can be encoded as a mathematical function or vice versa.
@user207442 You misunderstand. He doesn't want an array. He -ONLY- wants a mathematical function that is not backed by an array. If you believe you can, I would encourage you to write a mathematical function that returns the proper character of `this` comment given an integer of the index, but without backing it with an array or String or some similar construct. You would need to do a multi-order regression on the data points and it would generate a 400 something order equation. And that is simply an impractical solution to the problem.
glowcoder
@glowcoder I don't misunderstand at all. It's trivial to take your comment, pack it into a big fat integer, and write a function that extracts the characters one by one. No need for regression. I've written quines that meet far tougher requirements than this in my life. Been writing them all my life. Sorry, can't do it here with your comment. I only have 223 characters left.
@glowcode In fact, I can do better. I can convert any ASCII string you care to give me, up to 10000 characters say, into a *polynomial* evaluated modulo some prime bigger than 10000. Without regression. (http://tinyurl.com/psu6e if you don't know what 'modulo' means.)
+2  A: 

If you know how to encode an array as a function (you seem to be saying you already know how to do this) then the Kleene Recursion theorem guarantees it can be done.

But for doubting Thomases, here's a C example. It has a program generating function that uses only +, -, *, / or calls other functions that use them.

Quines are always possible if you have Turing completeness and freedom to print what you like.

A: 

To fly off at a tangent, try looking at Tupper's Self-Referential Formula.

High Performance Mark