[Prime]

Write a program that writes an exact copy of itself without using any outside references.

You can specify your own programming language.

It can define and use variables, assignment, and arithmetic: X = Y + 5, or X = "Myself".

It can use decision statements, such as IF, ELSE, SWITCH.

It can use any sequence of execution controls, like GOTO, or loops like DO WHILE, DO UNTIL, REPEAT x TIMES.

It can use WRITE, or PRINT to produce the output (its own text).

However, it cannot READ, nor it can refer to an absolute, or any outside address in memory. For that matter, let's prohibit the use of pointer variables.

No solutions over 10 lines long, please.

Perhaps, it is harder for people unfamiliar with computer programming to solve the problem. But I think, most anyone would easily understand the correct solution.

[Prime]

Now let's write a program that has

1. One or more "Head", or START statements in the beginning.

2. One or more "Tail", or END statements at the end.

3. Produces and exact and functional copy of itself.

The language is as Vimil has specified with few modifications:

1. START or HEAD statement must appear at the beginning of the program and may only be preceded by other START statements.

2. END or TAIL statements must appear at the very end and may not be followed by statements other than another END or TAIL.

3. DO(n) statement executes the command, which immediately follows it, n times.

4. PRINT statement prints everything on the line below. No other commands may follow PRINT on the same line. Everything on the line below is treated only as the text, which must be printed. Every time a PRINT statement is executed, it sends its output to a new line.

[unreality]

I have a hunch it's not possible, but maybe with Do(n)

[Guest]

argv[0] is the exe file name in c or c++

get date & time into a new string and append ".exe" to it

copy the file argv[0] to this new string

append this string to autoexexc.bat, win.ini, startup folders and at many places in the registry e.g. startup

You would make the Comp shutdown in a week with data being duplicated with very less time-slice for other work, may even run out of disk space as this will expand exponentially

[Guest]

argv[0] is the exe file name in c or c++

get date & time into a new string and append ".exe" to it

copy the file argv[0] to this new string

append this string to autoexexc.bat, win.ini, startup folders and at many places in the registry e.g. startup

You would make the Comp shutdown in a week with data being duplicated with very less time-slice for other work, may even run out of disk space as this will expand exponentially

Any volunteers ?

[Guest]

Now let's write a program that has

1. One or more "Head", or START statements in the beginning.

2. One or more "Tail", or END statements at the end.

3. Produces and exact and functional copy of itself.

The language is as Vimil has specified with few modifications:

1. START or HEAD statement must appear at the beginning of the program and may only be preceded by other START statements.

2. END or TAIL statements must appear at the very end and may not be followed by statements other than another END or TAIL.

3. DO(n) statement executes the command, which immediately follows it, n times.

4. PRINT statement prints everything on the line below. No other commands may follow PRINT on the same line. Everything on the line below is treated only as the text, which must be printed. Every time a PRINT statement is executed, it sends its output to a new line.

begin do(2) print

begin do(2) print

do(3) print

do(3) print

do(3) print

end

end

end

Edited September 8, 2008 by vimil

[Prime]

begin do(2) print

begin do(2) print

do(3) print

do(3) print

do(3) print

end

end

end

Vimil has the answer again!

Isn't it interesting, how program's need to propagate defines its tail size?

[EventHorizon]

Programs that produce exact copies of themselves are called "quines." In theory (due to the fixed-point theorem), every language has at least one. It was quite an interesting concept when we covered it in my computability and complexity theory class.

Here's some quines for C++......enjoy

1.

#include<iostream.h>

main(){char*s="#include<iostream.h>%cmain(){char*s=%c%s%c;cout.form(s,10,34,s,34,10);}%c";cout.form(s,10,34,s,34,10);}

2.

#include <iostream.h>

#define ENIUQ(TEMPLATE) cout << TEMPLATE << "(" << #TEMPLATE << ");}";

void main()

{ENIUQ("#include <iostream.h>\n#define ENIUQ(TEMPLATE) cout << TEMPLATE

<< \"(\" << #TEMPLATE << \");}\";\n\nvoid main()\n{ENIUQ");}

[EventHorizon]

...

In theory (due to the fixed-point theorem), every language has at least one.

...

What I meant is that every sufficiently powerful language has a quine. Obviously, you could easily dream up a language that does not have one, but it would be trivial/useless/intentionally handicapped. here's a quote from http://www.madore.org/~david/computers/quine.html.

"Any programming language which is Turing complete, and which is able to output any string (by a computable function of the string as program — this is a technical condition that is satisfied in every programming language in existence) has a quine program (and, in fact, infinitely many quine programs, and many similar curiosities) as follows by the fixed-point theorem. Moreover, the fixed-point theorem is constructive, so the construction of the quine is merely a matter of patience, not guesswork (or intelligence as some prefer to call it ;-). This is not to imply, of course, that actually writing a short or interesting quine may not demand a lot of cleverness. Still, it says that there is nothing “magical” behind quines; and also nothing says that they have to be obfuscated, difficult to read, or devoid of comments, as they often are."

Edited October 23, 2008 by EventHorizon

[Prime]

Programs that produce exact copies of themselves are called "quines." In theory (due to the fixed-point theorem), every language has at least one. It was quite an interesting concept when we covered it in my computability and complexity theory class.

Here's some quines for C++......enjoy

1.

#include<iostream.h>

main(){char*s="#include<iostream.h>%cmain(){char*s=%c%s%c;cout.form(s,10,34,s,34,10);}%c";cout.form(s,10,34,s,34,10);}

2.

#include <iostream.h>

#define ENIUQ(TEMPLATE) cout << TEMPLATE << "(" << #TEMPLATE << ");}";

void main()

{ENIUQ("#include <iostream.h>\n#define ENIUQ(TEMPLATE) cout << TEMPLATE

<< \"(\" << #TEMPLATE << \");}\";\n\nvoid main()\n{ENIUQ");}

It's fascinating. I had no idea there was so much theory on the subject.

But as far as this puzzle go, it meant to use a "handicap" language without all those possibilities. (Use of a loop was the whole trick.)

Your first example uses pointers. And the #TEMPLATE in the second example, appears to be a built in language device, which just solves the problem directly.

Another easy way would be just to read the file with the source code and write it out. But then it is not a puzzle.

[unreality]

i know this is a very old topic but I remembered it the other day while shoveling the driveway (I need something to think about whenver I'm doing anything mindless ) and tried to recall what vimil's solution had been and ended up reinventing the wheel so to speak for the quine:

do 2 print do 2 print

I defined 'do x cmd' as running 'cmd' x times. 'print' will print to the screen (on the same line always) everything that follows it, and assume that's the end of the line as everything that follows it is taken as a string.

When I finished the driveway, I defined a new language composed of ONLY 'do' and 'print' and each program can only be a single line. The next "iteration" a program is running the printed output from the previous iteration

these are some programs I made with it:

quine = do 2 print do 2 print

alternator = print do 2 print do 2

expander = do 3 print do 3 print

reducer = do 1 print do 1 print

I think the ONLY quine that can exist is "do 2 print do 2 print"... larger indexed ones grow infinitely and many others shrink to nonexistence by eventually printing a blank for the next generation

if there's some sort of virus with an extra command process called "attack" you could place it within the quine like this:

attack do 2 print attack do 2 print

this would attack, then print "attack do 2 print" twice to replicate itself... you could do any set of additional commands along with the replication if the commands are called "c" are placed exactly like this:

c do 2 print c do 2 print

then I thought... hmm, an ideal virus or digital organism would want to reproduce and continue existing, so maybe a command called "new" would create a new process and then subsequent "prints" would write to all open programs (the next generation of the current one plus all newly created ones). Thus a program that doubles each iteration:

new do 2 print new do 2 print

but what if the new program had to be "started up" with a command called 'run' (the current one just continues with the next generation)? Is it possible? You couldn't just do "new run" as it would run a blank program and then close it, dying off

i wonder what would happen if a program was created to simulate an environment of these organisms filled with random combinations of the commands (do, print, etc) and numbers after 'do' if necessary... then "releasing" them and seeing which ones survive. I may do that

[Prime]

i know this is a very old topic but I remembered it the other day while shoveling the driveway (I need something to think about whenver I'm doing anything mindless ) and tried to recall what vimil's solution had been and ended up reinventing the wheel so to speak for the quine:

do 2 print do 2 print

I defined 'do x cmd' as running 'cmd' x times. 'print' will print to the screen (on the same line always) everything that follows it, and assume that's the end of the line as everything that follows it is taken as a string.

When I finished the driveway, I defined a new language composed of ONLY 'do' and 'print' and each program can only be a single line. The next "iteration" a program is running the printed output from the previous iteration

these are some programs I made with it:

quine = do 2 print do 2 print

alternator = print do 2 print do 2

expander = do 3 print do 3 print

reducer = do 1 print do 1 print

I think the ONLY quine that can exist is "do 2 print do 2 print"... larger indexed ones grow infinitely and many others shrink to nonexistence by eventually printing a blank for the next generation

if there's some sort of virus with an extra command process called "attack" you could place it within the quine like this:

attack do 2 print attack do 2 print

this would attack, then print "attack do 2 print" twice to replicate itself... you could do any set of additional commands along with the replication if the commands are called "c" are placed exactly like this:

c do 2 print c do 2 print

then I thought... hmm, an ideal virus or digital organism would want to reproduce and continue existing, so maybe a command called "new" would create a new process and then subsequent "prints" would write to all open programs (the next generation of the current one plus all newly created ones). Thus a program that doubles each iteration:

new do 2 print new do 2 print

but what if the new program had to be "started up" with a command called 'run' (the current one just continues with the next generation)? Is it possible? You couldn't just do "new run" as it would run a blank program and then close it, dying off

i wonder what would happen if a program was created to simulate an environment of these organisms filled with random combinations of the commands (do, print, etc) and numbers after 'do' if necessary... then "releasing" them and seeing which ones survive. I may do that

I see, CR's concern was not unfounded...

The alternator will go into oblivion after 2 runs, same as the reducer.

I did not get the "attack". What is it?

Whreas "new" seems to be a command relying on some Operating System services for creating another copy of self. That clearly goes outside the scope of this puzzle.

In general, as EH has already pointed out, a good programming language has many possibilities for creating quines. This puzzle relied on limiting programming language capabilities.

[Guest]

I see, CR's concern was not unfounded...

Actually, it was...

The program is simply replicating itself, albeit exponentially.

In order to "launch Skynet", as it were, the program would have to become self-aware, as desire (to replicate and evolve) is a thoroughly organic concept.

But I digress.

[unreality]

prime: yeah I was going beyond the riddle, having 'new' represent whatever OS was actually being used. As for the alternator, I see my mistake now. Some sort of combination produced an alternator, but maybe I was mistaken.

That's a good task for the continuation of this riddle then: making an alternator out of do and print

[Prime]

Actually, it was...

The program is simply replicating itself, albeit exponentially.

In order to "launch Skynet", as it were, the program would have to become self-aware, as desire (to replicate and evolve) is a thoroughly organic concept.

But I digress.

Ah, but what is "self-aware"? What is "desire"? I say those are the terms to describe certain tendencies, the mechanism of which we cannot explain.

prime: yeah I was going beyond the riddle, having 'new' represent whatever OS was actually being used. As for the alternator, I see my mistake now. Some sort of combination produced an alternator, but maybe I was mistaken.

That's a good task for the continuation of this riddle then: making an alternator out of do and print

So, we have a new problem! Build an Alternator. That is program A, which outputs a different program B, which, in turn, begets program A.

I can see a solution.

Edited February 18, 2009 by Prime

[unreality]

it's a toughie - I came up with a few attempts, all of which failed:

print do 2 print do 2

do 2 print do 2

do 2 do 2

failz

(a few that grew exponentially)

so I decided to make a template:

state A

state B

both are in the form of either "print x" or "do y print x", where x printed (once OR y times) produces the other state

on a knack I dont think they can both start with "do", or at least don't have to. So the first one could start with print

print x

x must thus be a command that produces "print x"... I think I've found it: (half my template, half random insight)

print do 2 print print do 2 print

do 2 print print do 2 print

print do 2 print print do 2 print

do 2 print print do 2 print

etc

[Prime]

it's a toughie - I came up with a few attempts, all of which failed:

print do 2 print do 2

do 2 print do 2

do 2 do 2

failz

(a few that grew exponentially)

so I decided to make a template:

state A

state B

both are in the form of either "print x" or "do y print x", where x printed (once OR y times) produces the other state

on a knack I dont think they can both start with "do", or at least don't have to. So the first one could start with print

print x

x must thus be a command that produces "print x"... I think I've found it: (half my template, half random insight)

print do 2 print print do 2 print

do 2 print print do 2 print

print do 2 print print do 2 print

do 2 print print do 2 print

etc

That's the one! A true Alternator.

One side note. Here we redefine the print command to print without skipping to a new line.

[unreality]

That's the one! A true Alternator.

One side note. Here we redefine the print command to print without skipping to a new line.

yeah I redefined both print and do in this post:

I defined 'do x cmd' as running 'cmd' x times. 'print' will print to the screen (on the same line always) everything that follows it, and assume that's the end of the line as everything that follows it is taken as a string.

When I finished the driveway, I defined a new language composed of ONLY 'do' and 'print' and each program can only be a single line. The next "iteration" a program is running the printed output from the previous iteration

so we've got a quine and an alternator... I was thinking a program that started with x words ('word' being do, print or a number input of do) where x is a fibonacci number, and each iteration furthers the fibonacci sequence. It's tougher than the alternator and I think the fibonacci properites will have to be utilized... hmmm..